Learning the Structure of Hyperedge Replacement Graph Grammars

With the abundance of large sets of relational data, methods for analyzing and providing a compact representation of the data prove more important, yet these tasks are more difficult than with data having attribute value pairs. Graphs can be used to represent relational data, with nodes representing entities, and edges between nodes representing relationships between entities. To represent and analyze relational data, we focus on languages of graphs generated by context-free graph grammars with hyperedge replacement. Context-free graph grammars compactly represent sets of graphs. Given a set of graphs generated from an unknown context-free graph grammar, we can infer the productions of the original generating grammar. Our algorithm finds the correct right hand side candidates of the original grammar, and preserves the locations of non-terminal edges in the original grammar. We present the algorithm used to infer the productions, and perform experiments on both synthetic and real world datasets