GIKT: A Graph-Based Interaction Model for Knowledge Tracing

Yang Yang, Jian Shen, Yanru Qu, Yunfei Liu, Kerong Wang, Yaoming Zhu, Weinan Zhang, Yong Yu

Knowledge Tracing (KT) is the "holy grail" of personalized online education. It’s the task of modeling a student’s mastery of various concepts over time to predict how they’ll perform on the next challenge. While deep learning has pushed the boundaries of KT, most models struggle with a fundamental reality: students don't answer "skills," they answer specific "questions."

In this paper, researchers from Shanghai Jiao Tong University and UIUC introduce GIKT (Graph-based Interaction model for Knowledge Tracing). By leveraging Graph Convolutional Networks (GCNs), GIKT maps the intricate web of relationships between questions and skills, setting a new state-of-the-art benchmark in the field.

TL;DR

GIKT uses Graph Convolutional Networks to capture high-order correlations between questions and skills, combined with a "recap module" that selectively retrieves relevant past exercises. This dual approach allows the model to outperform existing methods by at least 1% in absolute AUC across major datasets.

What Problem Does This Paper Address?

Traditional KT models usually fall into one of two traps:

  1. The Skill-Only Trap: They track mastery of broad skills (e.g., "Multiplication"). However, two questions sharing the same skill can have vastly different difficulty levels or nuances.
  2. The Question Sparsity Trap: They try to track specific questions, but because there are thousands of questions and each student only answers a few, the data is too sparse to train a robust model.

Furthermore, standard sequence models like LSTMs often "forget" relevant exercises from a student's distant past or get bogged down by "noisy" recent exercises that aren't relevant to the current target question.

Methods

GIKT introduces three novel components to solve these issues:

  • Embedding Propagation via GCN: The authors represent the relationship between questions and skills as a bipartite graph. They use a GCN to propagate information across this graph. This means a question’s representation is enriched by the skills it requires, and a skill’s representation is enriched by all the questions associated with it. This effectively "smooths" the data, allowing the model to learn about rare questions through their related skills.
  • History Recap Module: To combat the "forgetting" problem, GIKT doesn't just rely on the final hidden state of an LSTM. Instead, it uses a "recap" mechanism to look back through the student's history and select the most relevant past exercises (either through "hard selection" of the same skills or "soft selection" via attention).
  • Generalized Interaction Module: Finally, the model doesn't just make a prediction based on the current state. It performs a pairwise interaction between the student’s current state, their retrieved history, the target question, and its related skills. An attention mechanism then weights these interactions to produce the final probability of a correct answer.

Datasets

The model was evaluated on three widely recognized benchmarks in the educational data mining community:

  • ASSIST09: A dataset from the ASSISTments platform (approx. 3.8k students, 123 skills).
  • ASSIST12: A larger version from the same platform (approx. 27k students, 265 skills).
  • EdNet: A massive-scale dataset from a mobile tutoring app (the authors used a subset of 5,000 students and 189 skills).

Key Insights and Ideas

  • High-Order Relations Matter: The ablation studies showed that increasing the number of GCN layers (up to 3) improved performance. This suggests that understanding the "friend-of-a-friend" relationships between questions and skills is vital for accurate tracing.
  • Exercises > Hidden States: One of the most interesting findings was that selecting specific past exercises for the recap module worked better than selecting past hidden states. The authors argue that hidden states often contain "noisy" or general information, whereas raw exercise history provides a cleaner signal for the specific question at hand.
  • Consistency is Key: By treating questions and skills as different "instantiations" of the same knowledge and interacting with them consistently, the model avoids the information loss seen in "skill-only" models.

Key Results

GIKT consistently outperformed all baselines, including popular models like DKT (Deep Knowledge Tracing) and DKVMN (Dynamic Key-Value Memory Networks).

  • AUC Improvement: GIKT achieved an absolute AUC improvement of at least 1% over the best-performing baselines across all three datasets.
  • Robustness to Sparsity: On the ASSIST09 dataset, where question-level data is particularly sparse, GIKT showed significant gains over question-only models (DKT-Q), proving the value of the GCN-based skill integration.

Limitations and Future Work

While GIKT is a significant step forward, the authors noted some complexities:

  • Soft Selection Refinement: In an addendum, the authors noted that their initial "soft selection" strategy for the recap module required further refinement to be truly effective, suggesting that how we "query" a student's memory is still an open research question.
  • Computational Complexity: GNNs and attention-based recap modules are computationally more expensive than simple RNNs. Scaling this to real-time systems with millions of users remains a challenge.

The authors suggest that future work could involve incorporating more "side information," such as the text of the questions or the specific time intervals between exercises, to further refine the student's knowledge state.

Summary updated

Abstract

With the rapid development in online education, knowledge tracing (KT) has become a fundamental problem which traces students' knowledge status and predicts their performance on new questions. Questions are often numerous in online education systems, and are always associated with much fewer skills. However, the previous literature fails to involve question information together with high-order question-skill correlations, which is mostly limited by data sparsity and multi-skill problems. From the model perspective, previous models can hardly capture the long-term dependency of student exercise history, and cannot model the interactions between student-questions, and student-skills in a consistent way. In this paper, we propose a Graph-based Interaction model for Knowledge Tracing (GIKT) to tackle the above probems. More specifically, GIKT utilizes graph convolutional network (GCN) to substantially incorporate question-skill correlations via embedding propagation. Besides, considering that relevant questions are usually scattered throughout the exercise history, and that question and skill are just different instantiations of knowledge, GIKT generalizes the degree of students' master of the question to the interactions between the student's current state, the student's history related exercises, the target question, and related skills. Experiments on three datasets demonstrate that GIKT achieves the new state-of-the-art performance, with at least 1% absolute AUC improvement.
BibTeX
@inproceedings{yang2020gikt,
  author = {Yang Yang and Jian Shen and Yanru Qu and Yunfei Liu and Kerong Wang and Yaoming Zhu and Weinan Zhang and Yong Yu},
  title = {{GIKT: A Graph-Based Interaction Model for Knowledge Tracing}},
  booktitle = {ECML/PKDD},
  year = {2020},
  doi = {10.1007/978-3-030-67658-2\_18},
}

Loading related content...

Figure