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:
- 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.
- 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