Measuring Interaction-Level Unlearning Difficulty for Collaborative Filtering
The growing emphasis on data privacy and user controllability mandates that recommendation models support the removal of specified data, known as recommendation unlearning. Although retraining is often regarded as the gold standard for machine unlearning, it is inadequate to attain complete unlearning in collaborative filtering recommendation due to interdependency between user-item interactions. We introduce interaction-level unlearning difficulty as a foresighted indicator of unlearning incompleteness after forgetting each interaction. Extensive experiments identify Embedding Entanglement Index and Subgraph Average Degree as interpretable difficulty indicators. They correlate strongly with membership-inference metrics and recommendation-specific effectiveness metrics. We further show that difficult requests require more related interactions to be extra deleted, while easier requests require fewer or no extra deletions.