Cross-Group Aligned Problem Difficulty Clustering Using Attention-Weighted Feature Learning

Technical Summary: Cross-Group Aligned Problem Difficulty Clustering Using Attention-Weighted Feature Learning

Problem Statement
Online Judge (OJ) platforms are critical infrastructure for programming education, providing vast repositories of problems and submission logs. However, a significant challenge in leveraging this data is learner heterogeneity: the same problem can be perceived as easy or difficult depending on a user's proficiency level. Existing difficulty categorization methods often rely on globally aggregated behavioral features, which obscure proficiency-dependent interaction patterns. Furthermore, standard clustering approaches applied independently to different user groups often yield inconsistent difficulty labels (e.g., a problem labeled "Easy" for advanced users might be labeled "Hard" for beginners), disrupting coherent learning progression. Additionally, OJ features (e.g., submission counts, attempts) are often highly skewed and long-tailed, potentially biasing distance-based clustering algorithms.

Methodology
The authors propose a proficiency-group-aware framework that integrates statistical modeling, attention-based feature learning, and cross-group alignment. The workflow consists of five primary stages:

1. Data Preprocessing and Feature Extraction:

   • Dataset: The study utilizes large-scale submission logs from the Aizu Online Judge (AOJ), comprising ~9.6 million submissions, 3,047 problems, and 83,495 users.
   • Rasch Modeling: A Rasch (1PL) model is fitted to binary submission outcomes (Accepted vs. Incorrect) to estimate latent user ability ($\theta$) and problem difficulty ($\beta$).
   • User Clustering: Users are clustered into three proficiency groups (Beginner, Intermediate, Advanced) based on their latent ability and accuracy using K-means.
   • Feature Construction: For each user group, problem-level features are aggregated, including:
     • Behavioral: Submissions, Average Attempts, Acceptance Rate, Average Time to Outcome.
     • Latent: Rasch-derived Difficulty Scores.
   • Preprocessing: To handle skewness and outliers, log-transformation is applied to submission counts, average attempts, and time-to-outcome. Z-score normalization is then used to map features to a common scale.

2. Attention-Based Difficulty Clustering (FA–K-means):

   • Instead of assuming uniform feature importance, the framework employs a Feature-Attention-guided K-means (FA–K-means) algorithm.
   • A feature-wise attention module learns group-specific weights ($A^{(g)}$) for each user group. This module uses a linear transformation followed by a tanh activation and a softmax function to generate attention scores, which are then used to create weighted feature representations ($Z^{(g)}$).
   • The module is trained via a reconstruction loss (minimizing the difference between input and reconstructed features) before applying K-means clustering on the weighted representations to identify difficulty levels (Easy, Medium, Hard).

3. Cross-Group Difficulty Alignment:

   • To address the inconsistency of labels across groups, a Global Difficulty Alignment step is introduced.
   • The method defines Non-Monotonic Ordering (NMO) as a metric for inconsistency, where a problem violates the expected order if $Difficulty_{Beginner} < Difficulty_{Intermediate} < Difficulty_{Advanced}$ is not maintained (assuming higher labels indicate higher difficulty).
   • The alignment process aggregates centroids of the same difficulty level across all groups to compute a "global difficulty center." These global centers are mapped back through each group's specific preprocessing and attention modules to create group-specific anchors. Problems are then reassigned to the closest anchor, ensuring a unified and monotonic difficulty scale across proficiency levels.

4. Evaluation:

   • Metrics: Clustering quality is evaluated using Silhouette Score (SS), Davies–Bouldin Index (DBI), and Calinski–Harabasz Index (CHI). Cross-group consistency is measured via NMO.
   • Baselines: The proposed method is compared against standard K-means, Fuzzy c-means (FCM), Ward's hierarchical clustering, and BIRCH.
   • Validation: Statistical significance is assessed using Kruskal-Wallis (KW) tests and effect sizes ($\epsilon^2$) to verify feature separation across clusters.

Key Contributions

• Proficiency-Aware Framework: The study introduces a framework that categorizes problem difficulty separately for three proficiency groups, capturing interaction patterns that population-level approaches miss.
• Formalization of NMO: The authors formalize Non-Monotonic Ordering (NMO) as an interpretable metric to quantify and minimize cross-group label inconsistency.
• FA–K-means Algorithm: The integration of feature-attention-guided K-means allows for the learning of group-specific adaptive feature weights, improving within-group clustering quality compared to standard uniform weighting.
• Global Alignment Strategy: A systematic alignment step is proposed to produce a unified difficulty scale, significantly reducing NMO.
• Interpretability: The framework identifies key features (specifically acceptance rate and average attempts) that drive difficulty separation, supported by statistical testing.

Experimental Results

• Clustering Quality: On the AOJ dataset, FA–K-means consistently outperformed baselines (K-means, FCM, Ward, BIRCH) across all proficiency groups. It achieved the highest Silhouette Scores (e.g., 0.42 for Beginners vs. 0.34 for K-means), highest Calinski–Harabasz Index, and lowest Davies–Bouldin Index.
• Cross-Group Consistency: The global alignment step drastically reduced NMO. For FA–K-means, NMO decreased from 30.41% (pre-alignment) to 9.69% (post-alignment). This was a superior reduction compared to baselines, which remained in the 21.50%–26.63% range post-alignment.
• Feature Importance: Attention weight analysis and KW tests identified Acceptance Rate and Average Attempts as the most significant indicators for distinguishing difficulty levels.
• Generalizability: Experiments on a synthetic dataset (generated via rank-based Gaussian copula) reproduced the AOJ findings, confirming the framework's stability and the robustness of the attention-based reweighting and alignment strategies.
• Visualization: A lightweight web-based dashboard was developed to demonstrate user-level inspection of the derived difficulty levels.

Significance and Claims
The paper claims that the proposed framework provides an effective and interpretable basis for group-aware difficulty categorization in OJ-based programming education. By acknowledging that difficulty is relative to user proficiency, the method offers a more coherent difficulty scale than global aggregation. The authors assert that their approach not only improves clustering validity metrics but also produces difficulty labels that remain consistent across learner groups, thereby supporting better learning progression for students and more informed problem organization for instructors. The study emphasizes that while the framework is validated on AOJ, its design is scalable and applicable to other domains with heterogeneous user groups and shared tasks. The authors remain modest regarding limitations, noting that the framework relies on submission-derived features and that performance may vary across platforms with different data sparsity or feature characteristics.