The central goal of educational datamining is to derive crucial pedagogical insights from student, course, and tutorial data. Real-world educational datasets are complex and heterogeneous comprising relational structures, social connections, demographic information, and long-term assignments. In this paper I describe Augmented Graph Grammars a robust formalism for graph rules that provides a natural structure for evaluating complex heterogeneous graph data. I also describe AGG an Augmented Graph Grammar engine written in Python and brie y describe its use.
The central goal of educational datamining is to draw pedagogical insights from real-world student data, insights which can inform instructors, students, and other researchers. While robust analytical formalisms have been de ned for categorical, numerical, and relational data most real-world educational data is complex and heterogeneous combining textual, numerical, and relational features. In large course settings such as a lecture course or MOOC, for example, students may form dynamic working groups and collaborate on complex assignments. They may also be given a exible set of reading, writing, or problem-solving tasks that they can choose to complete in any order. This process data can be encoded as a graph with nodes representing individual assignments and reading materials and arcs representing group relationships or traversal order. In order to capture important features of this rich graph data and to identify key relationships between teamwork, written text, and performance, it is necessary to apply a rule structure that can capture them naturally.
Individual student assignments can also contain
heterogeneous data. Argument diagrams, for example, have been
used to teach writing, argumentation, and scienti c
reasoning [
A sample student-produced argument diagram drawn from
my thesis work at the University of Pittsburgh is shown
in Figure 1. This work focused on the use of argument
diagrams to support students in developing written
scienti c reports and in identifying pedagogically-relevant
diagram structures that can be used to predict students'
subsequent performance (see [
This diagram contains a number of pedagogically-relevant
issues. Some of them are purely structural such as the
disjoint hypothesis node, and the fact that the supporting and
opposing arcs are drawn from the claim to the citations and
not vice-versa. It also contains more complex semantic
issues such as the fact that the text elds on the arcs contain
summary information for the cites not explanations of the
relationship, and the fact that the opposing citations,
citations that disagree about the central claim node have not
been distinguished from one-another via a comparison arc.
Problems such as these can be detected via complex rules,
and I have previously shown that the presence of such
problems are predictive of students' subsequent performance [
Automatic graph analysis is central to a number of research
domains including strategy transfer in games [
My focus in the present work is on the development of graph
rules that is logical graph patterns that match arbitrary
graph structures based upon content and structure
information. While arbitrary graph matching is NP-Hard (see [
Graph Grammars, as described by Rekers and Schurr, are
formal grammars whose atomic components are graphs or
graph elements, and whose productions transpose one graph
to another [
De nition 3.6 A graph grammar GG is a tuple (A; P ), with A a nonempty initial graph (the axiom), and P a set of graph grammar productions. To simplify forthcoming de nitions, the initial graph A will be treated as a special case of a production with an empty left-hand side. The set of all potential production instances of GG is abbreviated with P I(GG).
De nition 3.2 A (graph grammar) production p := (L; R) is a tuple of graphs over the same alphabets of vertex and edge labels LV and LE. Its left-hand side lhs(p) := L and its right-hand side rhs(p) := R may have a common (context) subgraph K if the following restrictions are fullled: 8e 2 E(K) ) s(e) 2 V (K) ^ t(e) 2 E(K) with E(K) := E(L) \ E(R) and V (K) := V (L)\V (R) i.e. sources and targets of common edges are common verticies of L and R, too. 8x 2 L\R ) lL(x) = lR(x) i.e. common elements of L and R do not di er with respect to their labels in L and R.
Thus graph grammars are systems of production rules
analogous to context-sensitive string grammars (see [
Let Gi =< fno; : : :g; fe(np; nq); : : :g > and Gj =< fmo; : : :g; fe(mk; ml); : : :g > be graphs and let M = f< na; M b > : : :g me a mapping from Gi to Gj that links nodes of the two. In the context of a mapping, Gi and Gk are called the source and target graphs respectively. A mapping MGi;Gj from Gi to Gj is valid if and only if the following holds: 8nx 2 Gi : 9 < nx; my >2 MGi;Gj :9f< nx; my >; < nr; mk >g
MGi;Gj : (x = r) _ (y = k) 8e(nx; ny) 2 Gi : f< nx; my >; < nr; mk >g : 9e(my; mk) 2 Gj MGi;Gj For the remainder of this paper all elements in a source graph will be labeled alphabetically (e.g. a, Q) while elements in the target graphs will be referenced numerically (e.g. 1; 2; e(2; 3); e(4; !5)).
Augmented Graph Grammars are a richer formalism for graph
rules that treat nodes and arcs as complex components with
optional sub- elds including exible text elements or other
types. Augmented graph grammars have been previously
described by Pinkwart et al. in [
In a simple graph grammar of the type used by Rekers and Schurr the set of possible node and arc types (P) is xed with the elements being atomic, static, and unique. In order to process complex structures such as the argument diagram shown in Figure 1, a more complex structure is required. Thus augmented graph grammar ontologies are de ned by a set of element types O = fN0; : : : Nm; E0; : : : ; Epg such that each element has a unique list of elds and eld types as well as applicable functions over those elds. The ontology must also specify appropriate relationships between the elds and operations that can be used on them. {
Citation:{
Cite(String) Cite.Words(StringSet) Summary(String)
Summary.Words(StringSet) } }
If(String) If.Words(StringSet) Then(String)
Then.Words(StringSet) } Arcs:{
Comparison: { ...
2. This illustrates the eld de nitions for the citation and hypothesis nodes shown above. Both node types contain two sub- elds of type String. For each of these elds an additional function is de ned '*.Words' which returns a set of all the words found in the eld.
The core component of an augmented graph grammar is the graph class. A class Ci is de ned by a 2-tuple < Si; Oi > where Si is a graph schema and Oi is a set of constraints. A class de nes a space of possible graphs which satisfy both the schema and the constraints. Classes are not required to be unique nor are the set of matching graphs for a given pair of classes required to be disjoint. A sample named class R07a is shown in 3. This class is designed to detect instances of Related Uncompared Opposition in scienti c argument diagrams. That is subgraphs where there exists a pair of citation nodes a, and b that disagree about a shared target node t, are not connected via a comparison arc c, and which share some relevant textual content. As I noted above, this type of structure can be found in Figure 1.
A Schema is a graph structure that de nes a space of possible graphs topologically. Schema are de ned by a set of ground nodes (e.g. t, a, & b in Figure 3) which must match a single node in a target graph, a set of ground arcs that must likewise match a single arc in the target graph (e.g. c), and an optional set of variable arcs which must match a nonempty subgraph de ned by a graph production. By convention, ground elements are denoted via lower-case names while variable elements are denoted by capitalized names. While showing a complete ontology is beyond the scope of this paper an illustrative example can be found in Figure In addition to the ground and variable distinctions arcs within a schema may be one of four types: directed (e.g. O, & (R07a) O
S a : c b 8 t:T ype 2 f\Hypothesis00; \Claim00g 9 >>>< ab::TTyyppee == \\CCiittaattiioonn0000 =>>> >:>>(a:summacr:yT:wypoerd=s \\Cb:osmumpamriasroyn:0w0ords) 6= ;>;>>
S ), of unknown direction, undirected (e.g. c), and undened. Directed arcs will only match directed arcs in the base graph oriented in the same direction. Thus, given a base graph containing an arc e(1; !2) and a schema with a directed arc e(n; m!) the schema will only match cases where f< n; 1 >; < m; 2 >g M . Unknown direction schema arcs may match a directed arc oriented in any order but will not match an undirected arc (e.g. e(2; 3)). Undirected arcs (e.g. :c) will not match a directed arc. And, unde ned arcs may match a directed or undirected arc in any order. As the example shows arcs may be also be negated (e.g. :c) in which case the schema matches a graph if and only if no match can be found for the negated arc. Thus the schema shown will only match ground graphs with no arc between the elements assigned to a and b. More complicated cases of negation may be formed using graph expressions which are de ned below.
The elements of a Schema must also be non-repeating that is, no two elements in a schema may be matched to the same element in the target graph. Thus each element in a schema must match at least one unique node or arc with variable elements possibly accounting for more than one element.
Constraints represent individual bounds or limits on the ground elements of a schema. Constraints are speci ed using a set-theory syntax (e.g. t:T ype 2 f\Hypothesis00; \Claim00g) and may draw on any of the node or arc features, sub elds, or functions speci ed in the ontology. Unary Constraints apply to a single element (e.g. a:T ype = \Citation00). Binary Constraints (e.g. (a:summary:words \ b:summary:words) 6= ;) specify a relationship between two distinct ground elements. (SC ) (SP 1) (SP 2) q q q:T ype = \Supporting00 q:T ype = \Supporting00 ! S(a; c) = [ Sc ) SP 1 [2; ] j
SP 2 ]
A graph production Cl ) Cr1jCr2::: is a context-sensitive production rule that maps from a graph class containing a single production variable to one or more alternate expansions. Graph productions are used to match layered subgraphs to the variable arcs. A simple recursive production rule for the variable element S(b; !t) is shown in Figure 4. The rule is de ned by the context class SC , and the two production classes SP 1 and SP 2. The context class is used as a key for the production application. It must contain exactly one variable arc, the production variable, and no constraints. The ground nodes a and c are context nodes and are used to ground the production for mapping. They must be present in all of the production rules. All production rules must be expansive with each of the production classes containing at least one ground element not present in the context class. Recursive productions are thus handled by iteratively grounding the mapping with additional context and, as per the non-repeating requirement, these rules must consume additional elements of the graph. Production rules are thus mapped in a layered fashion like the grammars de ned by Rekers and Schurr. h:T ype = \Hypothesis00 c
O
h (C0) (C1) h:T ype = \Hypothesis00 c:T ype = \Supporting00
8C0j:9C1 where each Ci is a graph class and each Si is a logical quanti er from the set: f8; :8; 9; :9g. The expressions allow for existential and universal scoping and arbitrary negation of graph classes. The expressions represent chained logical structures with each 'j' being read as \. . . such that . . . ". A sample graph expression is shown in Figure 5. This sample expression asserts that for all hypothesis nodes in the target graph there exist no citation nodes that oppose the target hypothesis. Thus it is a universal claim about a negated existential item. As this example illustrates graph expressions allow for more complex negation structures than are supported by the graph schema.
Graph expressions must be expansive or right-grounded such that the following constraints hold: 8Cm i>0 2 E : Ci 1 g Ci
Sm 2 f9; :9g
That is, the schema component of class Ci must be a
subgraph of all classes class Ci+n. This also holds true for
the constraints with all constraints present in class Ci
being present in classes Ci+n. And the rightmost class in the
expression must also be an existential (9) test with optional
negation.
3. AGG
AGG is a general-purpose augmented graph grammar
engine that implements recursive graph matching. The system
was developed in Python to support analysis of the
studentproduced argument diagrams described above. As such it is
exible, functions across platforms, and supports complex
graph ontologies and user-de ned functions. The system
was designed in a modular fashion and can be linked with
third-party libraries such as the NLTK [
At present the system uses a straightforward depth- rst stack matching algorithm. Given a graph and a set of named rules, de ned by a single graph class or expression, the system will rst match all ground nodes and arcs in the leftmost target class. Once each ground element has been matched then the system will recursively match all variable elements in the target. If at any point the system cannot continue to match elements it will pop up the stack and repeat. Rule matching is governed by the aforementioned restrictions of expansiveness and non-repetition. If a rule is de ned by a graph expression then each class match will set the context for subsequent rightmost matches. Rules de ned by a single class are complete once a single match is found. The system is designed to nd matches serially and can be called iteratively to extract all matching items.
In addition to basic graph grammars the AGG toolkit has
the capacity to de ne named rules. These are named graph
expressions or individual classes that will be recorded if they
match. In my thesis work, I applied the AGG engine to
develop a set of 42 such rules the scienti c argument diagrams.
These ranged in complexity from graph classes de ned by
a single node to more complex recursive expressions that
sought to identify disjoint subgraphs and unsupported
hypotheses. The example rules and expressions shown in
gures 3 - 5 were adapted from this set. The rules were used for
o ine processing of the graphs and for prediction of student
grades [
As part of the analysis process the rules were evaluated on a set of 526 diagrams containing between 0 and 41 nodes each. While exact e ciency data was not retained the performance of the rules varied widely depending upon their construction. General recursive rules such as a test for disjoint subgraphs performed quite ine ciently while smaller chained expressions were able to evaluate in a matter of seconds on a quad-core system.
The focus of this paper was on introducing Augmented Graph
Grammars and the AGG engine. The formalism provides for
a natural and robust representation of complex graph rules
for heterogeneous datasets. In prior work at the University
of Pittsburgh I applied Augmented Graph Grammars to the
detection of pedagogically relevant structures like Related
Uncompared Opposition (see Figure 3) in argument diagrams
of the type shown in Figure 1. The focus of that study was
on testing whether student-produced argument diagrams are
diagnostic of their ability to produce written argumentative
essays. The study was conducted in a course on
Psychological Research Methods at the University of Pittsburgh.
The graph features examined in that study included chained
counterarguments which feature chains of oppositional
information, and ungrounded hypotheses which are unrelated to
cited works, and so on. The study is described in detail in [
While the AGG system is robust more work remains to be done to make it widely available, and several open problems remain for future development. As noted above, arbitrary graph parsing is NP-Hard. Consequently, many rule classes are extremely ine cient. Despite this limitation, however, real e ciency gains may be made via parallelization and memoization. I am presently researching possible improvements to the system and plan to test them with additional datasets.
This work was supported by National Science Foundation Award No. 1122504, \DIP: Teaching Writing and Argumentation with AI-Supported Diagramming and Peer Review," Kevin D. Ashley PI with Chris Schunn and Diane Litman, co-PIs.