A Knowledge Graph Reasoning-Based Model for Computerized Adaptive Testing

Xinyi Qiu, Zhiyun ChenCOLING 2025

TL;DR

This paper introduces KGCAT, a novel approach to Computerized Adaptive Testing (CAT) that leverages knowledge graphs (KGs) to better understand the relationships between questions and concepts. By incorporating mutual information for concept disentanglement and a multi-objective reinforcement learning framework that considers question difficulty and student similarity, KGCAT significantly improves testing accuracy and interpretability.

What Problem Does This Paper Address?

Computerized Adaptive Testing (CAT) aims to personalize educational assessments by selecting questions that best estimate a student's knowledge level. While existing methods using Graph Neural Networks (GNNs) and Reinforcement Learning (RL) have shown promise, they often struggle with:

  • Handling concept relevance: When a question involves multiple concepts, it's challenging to determine the relative importance of each concept for accurate assessment. This can lead to "noise" from less relevant concepts affecting predictions.
  • Incomplete evaluation metrics: Traditional CAT models often focus on a single objective (like accuracy), neglecting other crucial factors such as question difficulty and student similarity, which are vital for effective learning and engagement.
  • Lack of interpretability: Understanding why a particular question was chosen can be difficult with black-box models.

This paper addresses these limitations by proposing a more sophisticated CAT model that explicitly models concept relationships and incorporates a richer set of objectives for question selection.

Methods

The proposed KGCAT model comprises two main modules:

  1. Knowledge Graph-Based State Encoder (KGSE):
    • Knowledge Graph Construction: Questions and concepts are represented as nodes in a knowledge graph, with edges indicating their relationships.
  2. Similarity-Aware Aggregation: To capture richer features, KGSE aggregates information from neighboring nodes in the KG. It uses a similarity metric to weigh the influence of neighbors, focusing on those with stronger connections.
  3. Mutual Information-Based Disentanglement: To mitigate noise from irrelevant concepts, a disentanglement module is introduced. It uses mutual information to decouple concept representations, ensuring that each concept component contributes independently and reducing interference from less relevant concepts.
  4. State Encoding: The student's historical interaction data is encoded into a state vector using a self-attention mechanism, which accounts for varying information content in correct vs. incorrect answers.
  5. Difficulty and Similarity-Based Multi-Objective Reinforcement Learning (DSMORL):
    • Multi-Objective Reward: Instead of a single reward, DSMORL uses a reward vector that includes accuracy, diversity, novelty, question difficulty, and student similarity.
  6. Question Difficulty Reward: This reward encourages selecting questions that are neither too easy nor too hard for the student, aiming to optimize learning.
  7. Student Similarity Reward: This reward promotes selecting questions that are similar to those a student has previously answered correctly or that are relevant to their learning trajectory, based on user similarity metrics (Jaccard coefficient).
  8. Actor-Critic Framework: An Actor-Critic reinforcement learning approach is employed to optimize the selection policy, balancing the multiple objectives.

Datasets

The experiments were conducted on three publicly available datasets:

  • Assist2009: A widely used dataset for educational data mining.
  • Junyi: Another dataset for educational assessments.
  • Eedi: A dataset specifically designed for educational applications.

These datasets were preprocessed by removing short interaction sequences (less than 40 interactions) and split into training, validation, and testing sets. Candidate and metadata sets were also created for each student to simulate real-time recommendation scenarios.

Key Insights and Ideas

  • Knowledge Graphs are Powerful for CAT: Explicitly modeling the semantic and relational information between questions and concepts using KGs provides a significant advantage over simpler GNN approaches.
  • Disentanglement is Crucial for Noise Reduction: Using mutual information to disentangle concept representations effectively reduces the impact of irrelevant concepts, leading to more accurate student state estimation.
  • Multi-Objective RL is Key for Holistic CAT: Incorporating question difficulty and student similarity into the reward function, alongside traditional metrics like accuracy, leads to more effective and personalized question selection. This moves beyond simply predicting correctness to optimizing the learning process.
  • Longer-Term Optimization Pays Off: While KGCAT might not always outperform baselines in very short test sequences, its reinforcement learning approach allows it to achieve superior performance over longer testing periods, reflecting its ability to optimize for sustained learning.

Key Results

KGCAT demonstrated superior performance across all three datasets, outperforming existing methods like MAAT, BOBCAT, NCAT, and GMOCAT in terms of AUC (Area Under the ROC Curve) and ACC (Accuracy). For instance, on the Assist2009 dataset at 20 steps, KGCAT achieved an AUC of 72.50 and an ACC of 69.75, which were the highest among the tested models. The paper also highlights that reinforcement learning-based models (including KGCAT) generally outperform non-RL methods in longer testing scenarios. Ablation studies confirmed that each component of KGCAT (KG, difficulty, and similarity rewards) contributes to its overall effectiveness.

Limitations and Future Work

The authors acknowledge a few limitations:

  • Scalability: Processing large-scale knowledge graphs with numerous concepts and questions can be computationally challenging, potentially limiting scalability.
  • Complexity: The integration of mutual information for disentanglement and the multi-objective RL framework introduces complexity in hyperparameter tuning, requiring significant effort to optimize learning rates, reward structures, and mutual information thresholds.

Future work could explore more efficient KG processing techniques and investigate methods for automating hyperparameter optimization in such complex models. The paper also suggests further exploration of the optimal projection number (K) for concept disentanglement.

Summary updated

BibTeX
@inproceedings{qiu2025knowledge,
  author = {Xinyi Qiu and Zhiyun Chen},
  title = {{A Knowledge Graph Reasoning-Based Model for Computerized Adaptive Testing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2025},
}
Figure