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 defined 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 flexible 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 scientific reasoning [10,2,19]. These structures reify real-world arguments as graphs using complex node and arc types to represent argumentative components such as hypothesis statements, citations, and claims. These complex elements can include types, text fields for short notes or free-text assertions, links to external resources, and other data.
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 scientific reports and in identifying pedagogically-relevant diagram structures that can be used to predict students' subsequent performance (see [8]). The diagram contains a central claim node representing a research claim. This node has a single text field in which the claim is stated. This is, in turn, connected to a set of citation nodes representing related work via a set of supporting, opposing, and undefined arcs colored green, red, and grey, respectively. The citation nodes each contain two text fields, one for the citation information and the other for a summary of the cited work, while the arcs contain a single text field for the warrant or explanation of why the relationship holds. At the top of the diagram there is a single disjoint hypothesis node which contains two text fields: a conditional or IF field, and a conditional or THEN field. 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 fields 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 [8,10,9]. This detection and remediation, however requires the development of rules that can incorporate complex structural and textual information. Automatic graph analysis is central to a number of research domains including strategy transfer in games [4], automatic recommendations [1], cheminformatics [12], and social network detection [11]. Graph analysis algorithms have been used to define educational communities [15,16,5]) and to automatically grade existing datasets [8,10,9]. Graphical structures have also been used in tutoring contexts to represent student work via argument diagrams of the type shown above (see [14,7] or to provide connection representations [19] for student guidance.
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 [18]) it is of practical importance, particularly in relational domains such as argument diagrams or student groups where our goal is to identify complex structures that may be evidence of deeper pedagogical issues. To that end, I will introduce Augmented Graph Grammars a robust rule formalism for complex graph rules and will describe AGG and augmented graph grammar engine for educational datamining. Both were developed as part of my thesis work at the University of Pittsburgh.
Graph Grammars, as described by Rekers and Schürr, are formal grammars whose atomic components are graphs or graph elements, and whose productions transpose one graph to another [17]. More formally, they define graph-grammars and productions as: Definition 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 definitions, 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). Definition 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 fulfilled:
. sources and targets of common edges are common verticies of L and R, too.
• ∀x ∈ L∩R ⇒ lL(x) = lR(x) i.e. common elements of L and R do not differ with respect to their labels in L and R.
Thus graph grammars are systems of production rules analogous to context-sensitive string grammars (see [18]). For reasons of efficiency Rekers and Schürr restrict their focus to layered graph-grammars where all productions must be expansive with the left-hand-side being a subgraph of the right. Classical graph grammars, like string grammars, assume a fixed alphabet of simple statically-typed node and arcs and can be used both to generate matching graphs programmatically or to parse matching graphs via mapping and decomposition. My focus in the present work is on graph matching which occurs via iterative mapping.
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),
Augmented Graph Grammars are a richer formalism for graph rules that treat nodes and arcs as complex components with optional sub-fields including flexible text elements or other types. Augmented graph grammars have been previously described by Pinkwart et al. in [13]. There the authors focused on the use of augmented graph grammars for tutoring. An Augmented Graph Grammar is defined by: a graph ontology that specifies the complex graph elements and functions available; a set of graph classes that define matching graphs; and optional graph productions and expressions that provide for recursive class mapping and logical scoping. I will describe each of these components briefly below. For a more detailed description see [8].
In a simple graph grammar of the type used by Rekers and Schürr the set of possible node and arc types ( ) is fixed 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 defined by a set of element types O = {N0, . . . Nm, E0, . . . , Ep} such that each element has a unique list of fields and field types as well as applicable functions over those fields. The ontology must also specify appropriate relationships between the fields and operations that can be used on them.
While showing a complete ontology is beyond the scope of this paper an illustrative example can be found in Figure 2. This illustrates the field definitions for the citation and hypothesis nodes shown above. Both node types contain two sub-fields of type String. For each of these fields an additional function is defined '*.Words' which returns a set of all the words found in the field.
The core component of an augmented graph grammar is the graph class. A class Ci is defined by a 2-tuple < Si, Oi > where Si is a graph schema and Oi is a set of constraints.
A class defines 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 scientific 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 defines a space of possible graphs topologically. Schema are defined 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 defined by a graph production. By convention, ground elements are denoted via lower-case names while variable elements are denoted by capitalized names.
In addition to the ground and variable distinctions arcs within a schema may be one of four types: directed (e. S ), of unknown direction, undirected (e.g. c), and undefined. 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 {< n, 1 >, < m, 2 >} ⊆ 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, undefined 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 defined 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 specified using a set-theory syntax (e.g. t.T ype ∈ {"Hypothesis , "Claim }) and may draw on any of the node or arc features, subfields, or functions specified in the ontology. Unary Constraints apply to a single element (e.g. a.T ype = "Citation ). Binary Constraints (e.g. (S P 1 ) q.T ype = "Supporting a c q (S P 2 )
Figure 4: A simple recursive rule production for S that defines a supporting path.
A graph production C l ⇒ Cr1|Cr2... 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 defined 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 defined by Rekers and Schürr.
Graph expressions are logical rules of the form:
where each Ci is a graph class and each Si is a logical quantifier from the set: {∀, ¬∀, ∃, ¬∃}. The expressions allow for existential and universal scoping and arbitrary negation of graph classes. The expressions represent chained logical structures with each '|' 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:
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 (∃) test with optional negation.
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 flexible, functions across platforms, and supports complex graph ontologies and user-defined functions. The system was designed in a modular fashion and can be linked with third-party libraries such as the NLTK [6].
At present the system uses a straightforward depth-first stack matching algorithm. Given a graph and a set of named rules, defined by a single graph class or expression, the system will first 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 defined by a graph expression then each class match will set the context for subsequent rightmost matches. Rules defined by a single class are complete once a single match is found. The system is designed to find 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 define 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 scientific argument diagrams. These ranged in complexity from graph classes defined 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 figures 3 -5 were adapted from this set. The rules were used for offline processing of the graphs and for prediction of student grades [10,9].
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 efficiency 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 inefficiently 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 [8], and a discussion of the empirical validity of the individual rules can be found in [9]. The rules were also used as the basis of predictive models for student grades described in [10].
The Augmented Graph Grammars were ideally-suited for this task as they allowed me to define clear and robust rules that incorporated the structural information in the graph, textual information within the nodes and arcs, and the static element types. It was also possible to clearly present these rules to domain experts for evaluation.
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 inefficient. Despite this limitation, however, real efficiency 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.