Graph Analysis of Student Model Networks Julio Guerra Yun Huang School of Information Sciences Intelligent Systems Program University of Pittsburgh University of Pittsburgh Pittsburgh, PA, USA Pittsburgh, PA, USA jdg60@pitt.edu yuh43@pitt.edu Roya Hosseini Peter Brusilovsky Intelligent Systems Program School of Information Sciences University of Pittsburgh University of Pittsburgh Pittsburgh, PA, USA Pittsburgh, PA, USA roh38@pitt.edu peterb@pitt.edu ABSTRACT same for all students and at all times. In this work we ex- This paper explores the feasibility of a graph-based approach plore the idea that it might be beneficial for a student model to model student knowledge in the domain of programming. to include connections between domain KEs that represent The key idea of this approach is that programming concepts some aspects of individual student knowledge rather than are truly learned not in isolation, but rather in combina- domain knowledge. This idea is motivated by the recogni- tion with other concepts. Following this idea, we represent tion that the mastery in many domains is reached as the a student model as a graph where links are gradually added student practices connecting different KEs, i.e., each KE is when the student’s ability to work with connected pairs of practiced in conjunction with other KEs. To address this, we concepts in the same context is confirmed. We also hypothe- build a model represented as a network of KEs that get pro- size that with this graph-based approach a number of tradi- gressively connected as the student successfully works with tional graph metrics could be used to better measure student problems and assessment items containing multiple KEs. As knowledge than using more traditional scalar models of stu- the student succeeds in more diverse items mapped to dif- dent knowledge. To collect some early evidence in favor of ferent KEs, her model gets better connected. this idea, we used data from several classroom studies to correlate graph metrics with various performance and moti- To explore the value of this graph-based representation of vation metrics. student knowledge, we compute different graph metrics (e.g., density, diameter) for each student and analyze them in re- 1. INTRODUCTION lation to student performance metrics and attitudinal ori- Student modeling is widely used in adaptive educational sys- entations drawn from a motivational theory. This analysis tems and tutoring systems to keep track of student knowl- was performed using data collected from 3 cohorts of a Java edge, detect misconceptions, provide targeted support and programming course using the same system and the same give feedback to the student [2]. The most typical overlay content materials. In the remaining part of the paper, we student model dynamically represents the inferred knowl- describe related work, introduce and illustrate the suggested edge level of the student for each knowledge element (KE) approach, describe graph and performance metrics, and re- (also called knowledge component or KC) defined in a do- port the results of the correlation analysis. main model. These knowledge levels are computed as the student answers questions or solves problems that are mapped to the domain KEs. Student models are frequently built over 2. RELATED WORK networked domain models where KEs are connected by pre- Graph representation of student activity is not new. The requisite, is-a, and other ontological relationships that are 2014 version of the Graph-Based Educational Data Mining used to propagate the knowledge levels and produce a more Workshop 1 contains two broad types of related work: the accurate representation of the knowledge of the learner. Since analysis of the networking interaction among students, for these connections belong to domain models, they stay the example work on social capital [14] and social networking in MOOCs [3, 12]; and analyses of learning paths over graph representation of student traces while performing activities in the system [1, 5]. Our work fits in the second type since we model traces of each student interacting with the sys- tem. However, our approach is different as it attempts to combine an underlying conceptual model with the traces of the student learning. 1 http://ceur-ws.org/Vol-1183/gedm2014_proceedings. pdf A considerable amount of work focused on graph repre- sentation of domain models that serve as a basis for over- lay student models. The majority of this work focused on constructing the prerequisite relationships between domain knowledge components (concept, skills) [6, 13]. In this case links established between a pair of concepts represent prereq- uisite - outcome relationship. Another considerable stream of work explored the use of formal ontologies with such re- lationships as is-a and part-of for connecting domain knowl- edge components [7]. Ontological representation, in turn, relates to another stream of work that applies graph tech- niques to structural knowledge representation, for example by analyzing the network properties of ontologies [9]. Figure 1: Exercise jwhile1 The research on graph-based domain models also leads to a stream of work on using Bayesian networks to model the relationships between domain concepts for knowledge prop- path length, and average node weight can be good indicators agation in the process of student modeling [15, 4]. Yet, in of student knowledge compared to the amount of activities both cases mentioned above links between knowledge com- done or overall measures of assessment like success rate on ponents were not parts of individual student model, but ei- exercises. We further explore these graph metrics in relation ther parts of the domain model or student modeling pro- with motivational factors drawn from a learning motivation cess and thus remain the same for all students. In con- theory. trast, the approach suggested in this paper adds links be- tween knowledge components to individual student models 3.1 Domain Model and Content to express combinations of knowledge components that the Our content corpus is composed by a set of 112 interactive given student explored in a problem solving or assessment parameterized exercises (i.e., questions or problems) in the process. This approach is motivated by our belief that in domain of Java programming from our system QuizJet [11]. the programming domain, student knowledge is more effec- Parameterized exercises are generated from a template by tively modeled by capturing student progress when students substituting a parameter variable with a randomly generated needed to apply multiple concepts at the same time. value. As a result each exercise can be attempted multiple times. To answer the exercise the student has to mentally 3. THE APPROACH execute a fragment of Java code to determine the value of a The idea behind our approach is that knowledge is likely to specific variable or the content printed on a console. When be stronger for concepts which are practiced together with the student answers, the system evaluates the correctness, a larger variety of other concepts. We hypothesize, for ex- reports to the student whether the answer was correct or ample, that a student who solves exercises, in which the wrong, shows the correct response, and invites the student concept for-loop is used with post-incremental operator and to “try again”. As a result, students may still try the same post-decremental operator will have a better understanding exercises even after several correct attempts. An example of of for-loop than another student who practices (even the parameterized java exercise can be seen in Figure 1. same amount of times) the for loops concept in a more nar- row context, i.e., only with post-incremental operator. To In order to find the concepts inside all of the exercises, we represent our approach, for each student we build a graph- used a parser [10] that extracts concepts from the exercise’s based student model as a network of concepts where the template code, analyzes its abstract syntax tree (AST), and edges are created as the student succeeds in exercises con- maps the nodes of the AST (concepts extracted) to the nodes taining both concepts to be connected. The Domain Model in a Java ontology 2 . This ontology is a hierarchy of pro- defining the concept space and the mapping between the gramming concepts in the java domain and the parser uses concepts and programming exercises is explained in the next only the concepts in the leaf nodes of the hierarchy. section. The weight of the edges in the graph is computed as the overall success rate on exercises performed by the In total there are 138 concepts extracted and mapped to student which contain the pair of concepts. Pairs of con- QuizJet exercises. Examples of concepts are: Int Data Type, cepts that do not co-occur in exercises succeeded by the stu- Less Expression, Return Statement, For Statement, Subtract dent are not connected in her graph. In this representation, Expression, Constant, Constant Initialization Statement, If highly connected nodes are concepts successfully practiced Statement, Array Data Type, Constructor Definition, etc. with different other concepts. We also compute a measure We excluded 8 concepts which appear in all exercise tem- of weight for each node by taking the average weight among plates (for example “Class Definition” or “Public Class Spec- edges connecting the node. This measure of the success rate ifier” appear in the first line of all exercises). Each concept on concepts favors exercises that connect more concepts be- appears in one or more Java exercises. Each of the 112 ex- cause each exercise containing n concepts produce or affects ercises maps to 2 to 47 Java concepts. For example, the n(n − 1)/2 edges. For example, a success on an exercise hav- exercise “jwhile1”, shown in Figure 1, is mapped to 5 con- ing 10 concepts contributes to 45 edges, but a successful at- cepts: Int Data Type, Simple Assignment Expression, Less tempt to an exercise connecting 5 concepts only contributes Expression, While Statement, Post Increment Expression. to 10 edges. We hypothesize that in a graph built following 2 this approach, metrics like average degree, density, average http://www.sis.pitt.edu/~paws/ont/java.owl 3.2 Graph Metrics Table 1: Correlation between activity measures and grade To characterize the student knowledge graph we computed and between graph metrics and grade. * significance at 0.1, standard graph metrics listed below. ** significance at 0.05. Measure of Activity Corr. Coeff. Sig. (p) • Graph Density (density): the ratio of the number of Correct Attempts to Exercises .046 .553 edges and the number of possible edges. Distinct Correct Exercises .114 .147 • Graph Diameter (diameter): length of the longest Overall Success Rate .298 .000** shortest path between every pair of nodes. Avg. Success Rate on Concepts .188 .016** • Average Path Length (avg.path.len): average among the shortest paths between all pairs of nodes. Graph Metric Corr. Coeff. Sig. (p) • Average Degree (avg.degree): average among the Average Degree .150 .055* degree of all nodes in an undirected graph. Graph Density .102 .190 • Average Node Weight (avg.node.weight): the weight Graph Diameter .147 .081 of a node is the average of the weight of its edges. We Average Path Length .152 .052* then average the weights of all nodes in the graph. Average Node Weight .201 .010** 3.3 Measures of Activity To measure student activity so that it could be correlated 4. EXPERIMENTS AND RESULTS with the graph metrics we collected and calculated the fol- 4.1 Dataset lowing success measures: We collected student data over three terms of a Java Pro- gramming course using the system: Fall 2013, Spring 2014, • Correct Attempts to Exercises (correct.attempts): and Fall 2014. Since the system usage was not mandatory, total number of correct attempts to exercises. It in- we want to exclude students who just tried the system while cludes repetition of exercises as well. likely using other activities (not captured by the system) • Distinct Correct Exercises (dist.correct.attempts): for practicing Java programming. For this we looked at the number of distinct exercise attempted successfully. distribution of distinct exercises attempted and we exclude • Overall Success Rate (success.rate): the number all student below the 1st quartile (14.5 distinct exercises of correct attempts to exercises divided by the total attempted). This left 83 students for our analysis. In to- number of attempts. tal these students made 8,915 attempts to exercises. On • Average Success Rate on Concepts average, students have attempted about 55 (Standard Devi- (avg.concept.succ.rate): we compute the success rate ation=22) distinct exercises while performing an average of of each concept as the average success rate of the ex- 107 (SD=92) exercises attempts. On average, students have ercises containing the concept. Then we average this covered about 63 concepts with SD=25 (i.e., succeeded in at among all concepts in the domain model. least one exercise containing the concept), and have covered about 773 concept pairs with SD=772 (i.e., succeeded in at least one exercise covering the concept pair.) The average 3.4 Motivational Factors success rate ( #correct attempts ) across students is about 69% We use the revised Achievement-Goal Orientation question- #total attempts naire [8] which contains 12 questions in a 7-point Likert (SD=11%). scale. There are 3 questions for each of the 4 factors of the Achievement-Goal Orientation framework : Mastery - 4.2 Graph Metrics and Learning Approach, Mastery-Avoidance, Performance-Approach and We compare graph metrics (Avg. Degree, Graph Density, Performance-Avoidance. Mastery-Approach goal orien- Graph Diameter, Avg. Path Length and Avg Node Weight) tation relates to intrinsic motivation: “I want to learn this and measures of activity (Correct Attempts to Exercises, because it is interesting for me”, “I want to master this Distinct Correct Exercises, Overall Success Rate and Avg. subject”; Mastery-Avoidance relates to the attitude of Success Rate on Concepts) by computing the Kendall’s τB avoid to fail or avoid learning less than the minimum; Per- correlation of these metrics with respect to the students’ formance -Approach goal orientation stresses the idea of grade on the programming course. Results are displayed in having a good performance and relates well with social com- Table 1. parison: “I want to perform good in this subject”, “I want to be better than others here”; and Performance-Avoidance Surprisingly, the plain Overall Success Rate (which does oriented students avoid to get lower grades or avoid to per- not consider concepts disaggregation, nor graph informa- form worse than other students. The goal orientation of tion) is better correlated with course grade than any other a student helps to explain the behavior that the student measure. Students who succeed more frequently, get in gen- exposes when facing difficulty, but does not label the final eral better grades. Interestingly, both the Average Suc- achievement of the student. For example, if a student is cess Rate on Concepts and the Average Node Weight Mastery-Approach oriented, it does not necessarily mean are both significantly correlated with grade. This last mea- that the student reached the mastery level of the skill or sure uses the graph information and presents a slightly bet- knowledge. In our case, we believe the achievement-goal ori- ter correlation than the former, which does not consider the entation of the student can convey the tendency to pursue graph information. (or avoid) to solve more diverse (and more difficult) exer- cises, which contain more heterogeneous space of concepts, Among the other graph metrics, Average Degree and Av- thus contribute to form better connected graphs. erage Path Length are marginally correlated with course which extent the motivational profile of the student explains the graph’s shape. Step-wise regression models were used where the dependent variables are the graph metrics and the independent variables are the motivational factors. We found a significant model of the diameter of the graph (R2 = 0.161, F = 6.523, p = 0.006) with the factors Mastery- Avoidance (B = 0.952, p = 0.001) and Mastery-Approach (B = −0.938, p = 0.006). Note the negative coefficient for Mastery-Approach and the positive coefficient for Mastery- Avoidance. As the Achievement-Goal Orientation frame- Figure 2: Graph representation of two students. work suggests, Mastery-Approach oriented students are mo- tivated to learn more, tend to explore more content and do not give up easily when facing difficulties; Mastery-Avoidance Table 2: Graph metrics, measures of activity and motiva- students, in the other hand, do not cope well with diffi- tional scores of 2 students. culties and tend to give up. Then, a possible explanation Student A Student B of the results is that, in one hand, students with higher Graph Density 0.077 0.094 Mastery-Approach orientation are more likely to solve diffi- Graph Diameter 2.85 2.00 cult questions which connects more and more distant con- Avg. Path Length 1.77 1.78 cepts which decreases the graph diameter; and on the other Avg. Degree 8.64 10.55 hand, Mastery-Avoidance students avoid difficult exercises Avg. Node Weight 0.49 0.51 containing many concepts, thus making less connections and Correct Attempts 71 83 producing graphs with higher diameters. Correlations be- Dist. Correct Exercises 66 61 tween graph metrics and motivational factors confirmed the Overall Succ. Rate 0.82 0.76 relation between Mastery-Avoidance and Graph Diameter Avg. Succ.Rate on Concepts 0.50 0.53 (Kendall’s τB = 0.197, p = 0.030). Although these re- Mastery-Approach 0.83 0.78 sults are encouraging, they are not conclusive. For exam- Mastery-Avoidance 0.83 0.56 ple, Mastery-Approach students might just do more work, Performance-Approach 1.0 0.17 not necessarily targeting difficult questions. More analysis Performance-Avoidance 1.0 0.0 is needed to deeply explore these issues. Grade (%) 100 97 5. DISCUSSIONS AND CONCLUSIONS In this paper we proposed a novel approach to represent stu- grade (p values less than 0.1). Although this is a weak ev- dent model in the form of a dynamic graph of concepts that idence, we believe that we are in the good track. A higher become connected when the student succeed in assessment Average Degree means a better connected graph, thus it item containing a pair of concepts to be connected. The follows our idea that highly connected nodes signal more idea behind this approach is to strengthen the model for knowledge. Average Path Length is more difficult to in- those concepts that are applied in more different contexts, terpret. A higher Average Path Length means a less i.e., in assessment items containing other different concepts. connected graph (which contradicts our assumption), but We applied this approach to data of assessment items an- also, it can express students reaching more “rear” concepts swered by real students and analyzed the graph properties which appear in few more-difficult-exercises and generally comparing them to several performance measures such as have longer shortest paths. We think that further explo- course grade as well as motivational factors. Results showed ration of metrics among sub-graphs (e.g. a graph for an that this idea is potentially a good indicator of knowledge specific topic), and further refinement of the approach to of the students, but further refinement of the approach is build edges (e.g. connecting concepts that co-occur close to needed. We used several measures of the built graphs as each other in the exercise) could help to clarify these results descriptors of student knowledge level, and we found that a metric aggregating the success rates of the edges to the level Figure 2 shows the graphs of 2 students who have similar of concepts (nodes) is highly correlated to course grade, al- amount of distinct exercises solved correctly but present dif- though it does not beat the plain overall success rate of the ferent graph metrics and motivational profile. See metrics in student in assessment items. Table 2. Student B has more edges, lower diameter, higher density, higher degree, solved less questions more times. Stu- In the future work, we plan to repeat our analysis using dent A presents a less connected graph although she he/she more reliable approaches to construct the knowledge graph. solved more distinct questions (66 compared to 61 on Stu- One idea is to use rich information provided by the parser dent B). Student B has lower Mastery-Avoidance orientation (mapping between exercises and concepts) to ensure that score and lower Performance orientation scores than Student each new link connects concepts that interact considerably A, which could explain why Student B work result in a bet- in the program code. This could be done by controlling ter connected graph. Analyses of Motivational factors are the concepts proximity in the question code (e.g. only con- described in the following section. sider co-occurrence when concepts are close to each other in the parser tree.) Another approach to keep more reliable 4.3 Metrics and Motivation edges is to consider only a subset of important concepts We now explore the relationship between motivational fac- for each problem using feature selection techniques. Also tors and the graphs of the students. The idea is to see to we plan to perform analyses of sub-graphs targeting specific “zones” of knowledge. For example, a partial graph with [7] P. Dolog, N. Henze, W. Nejdl, and M. Sintek. The only concepts that belongs to a specific topic, or concepts personal reader: Personalizing and enriching learning that are prerequisites of a specific concept. Another inter- resources using semantic web technologies. In esting idea relates to recommendation of content: guide the P. De Bra and W. Nejdl, editors, Adaptive Hypermedia and Adaptive Web-Based Systems, volume 3137 of student to questions that will connect the isolated parts of Lecture Notes in Computer Science, pages 85–94. the knowledge graph or minimize the average path length of Springer Berlin Heidelberg, 2004. the graph. Along the same lines, the analysis of the graph [8] A. J. Elliot and K. Murayama. On the measurement shortest paths and overall connectivity can help in designing of achievement goals: Critique, illustration, and assessment items that better connect distant concepts. application. Journal of Educational Psychology, 100(3):613, 2008. [9] B. Hoser, A. Hotho, R. Jäschke, C. Schmitz, and 6. REFERENCES G. Stumme. Semantic network analysis of ontologies. [1] N. Belacel, G. Durand, and F. Laplante. A binary Springer, 2006. integer programming model for global optimization of [10] R. Hosseini and P. Brusilovsky. Javaparser: A learning path discovery. In Workshop on Graph-Based fine-grain concept indexing tool for java exercises. In Educational Data Mining. The First Workshop on AI-supported Education for [2] P. Brusilovsky and E. Millán. User models for Computer Science (AIEDCS 2013), pages 60–63, 2013. adaptive hypermedia and adaptive educational [11] I.-H. Hsiao, S. Sosnovsky, and P. Brusilovsky. Guiding systems. In P. Brusilovsky, A. Kobsa, and W. Nejdl, students to the right questions: adaptive navigation editors, The Adaptive Web, volume 4321 of Lecture support in an e-learning system for java programming. Notes in Computer Science, chapter 1, pages 3–53. Journal of Computer Assisted Learning, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. 26(4):270–283, 2010. [3] V. Cateté, D. Hicks, C. Lynch, and T. Barnes. [12] S. Jiang, S. M. Fitzhugh, and M. Warschauer. Social Snag’em: Graph data mining for a social networking positioning and performance in moocs. In Workshop game. In Workshop on Graph-Based Educational Data on Graph-Based Educational Data Mining, page 14. Mining, volume 6, page 10. [13] T. Käser, S. Klingler, A. G. Schwing, and M. Gross. [4] C. Conati, A. Gertner, and K. Vanlehn. Using Beyond knowledge tracing: Modeling skill topologies bayesian networks to manage uncertainty in student with bayesian networks. In Intelligent Tutoring modeling. User modeling and user-adapted interaction, Systems, pages 188–198. Springer, 2014. 12(4):371–417, 2002. [14] V. Kovanovic, S. Joksimovic, D. Gasevic, and [5] R. Dekel and Y. Gal. On-line plan recognition in M. Hatala. What is the source of social capital? the exploratory learning environments. In Workshop on association between social network position and social Graph-Based Educational Data Mining. presence in communities of inquiry. 2014. [6] M. C. Desmarais and M. Gagnon. Bayesian student [15] E. Millán, T. Loboda, and J. L. Pérez-de-la Cruz. models based on item to item knowledge structures. Bayesian networks for student model engineering. Springer, 2006. Computers & Education, 55(4):1663–1683, 2010.