Augmented Graph Grammars (AGGs) are a robust rule formalism for graphs that allow for complex node and arc types, optional substructures, and complex rule expressions. Rather than using a fixed alphabet of graph components they are defined by a complex ontology that allows for subsidiary types such as textual fields, access functions, and directional information. They can also be used to evaluate negated elements as well as quantified expressions. As such they are better suited to complex graph data (e.g student-produced argument diagrams, complex social networks and chemical data).

Research has shown that hand-authored graph grammars can be used to automatically grade argument diagrams. Argument diagrams are graphical representations that reify key features of arguments such as hypothesis statements, claims, and citations as nodes and the supporting, opposing, and clarification relationships between them as arcs.

In this work, we applied Evolutionary Computation (EC) to automatically induce two types of empirically-valid graph grammars for student-produced argument diagrams. The positive-correlated graph rules are good structural features, and the negative-correlated graph rules indicate the structural flaws in students’ work. We showed that the induced graph rules outperform the expert rules and they outperform all of the rules induced by two general purpose graph grammar induction algorithms, Subdue and gSpan.

The significance of this project is that the induced graph rules can be used for automatic grading and providing the basis for hints.