<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>In this paper we study the inference of node and edge replacement graph grammars. We search for frequent subgraphs and then check for an overlap among the instances of the subgraphs in the input graph. If the subgraphs overlap by one node, we propose a node replacement graph grammar production. If the subgraphs overlap by two nodes or two nodes and an edge, we propose an edge replacement graph grammar production. We can also infer a hierarchy of productions by compressing portions of a graph described by a production and then inferring new productions on the compressed graph. We validate the approach in experiments where we generate graphs from known grammars and measure how well the approach infers the original grammar from the generated graph. We show graph grammars found in biological molecules, biological networks, and analyze learning curves of the algorithm.</p></abstract>

In this paper we study the inference of node and edge replacement graph grammars. We search for frequent subgraphs and then check for an overlap among the instances of the subgraphs in the input graph. If the subgraphs overlap by one node, we propose a node replacement graph grammar production. If the subgraphs overlap by two nodes or two nodes and an edge, we propose an edge replacement graph grammar production. We can also infer a hierarchy of productions by compressing portions of a graph described by a production and then inferring new productions on the compressed graph. We validate the approach in experiments where we generate graphs from known grammars and measure how well the approach infers the original grammar from the generated graph. We show graph grammars found in biological molecules, biological networks, and analyze learning curves of the algorithm.

Inferring Graph Grammars by Detecting Overlap in Frequent Subgraphs

Dana-Farber/Brigham and Women's Cancer Center, Harvard Medical School, 75 Francis Street, Boston, MA 02115, USA

School of Electrical Engineering and Computer Science, Washington State University, Box 642752, Pullman, WA 99164, USA

International Journal of Applied Mathematics and Computer Science

{"article-title":"Inferring Graph Grammars by Detecting Overlap in Frequent Subgraphs"}

In this paper we study the inference of node and edge replacement graph grammars. We search for frequent subgraphs and then check for an overlap among the...

Inferring Graph Grammars by Detecting Overlap in Frequent Subgraphs

Published Online: Jun 16, 2008

Page range: 241 - 250

DOI: https://doi.org/10.2478/v10006-008-0022-y

Keywords
grammar induction, graph grammars, graph mining, multi-relational data mining

This content is open access.

Inferring Graph Grammars by Detecting Overlap in Frequent Subgraphs

Published Online: Jun 16, 2008

Page range: 241 - 250

DOI: https://doi.org/10.2478/v10006-008-0022-y

Keywordsgrammar induction, graph grammars, graph mining, multi-relational data mining

This content is open access.

Keywords
grammar induction, graph grammars, graph mining, multi-relational data mining