# Measuring the Predictability of Recommender Systems using Structural Complexity Metrics

arXiv: https://arxiv.org/abs/2404.08829 · HTML: https://mlsanity.com/paper/2404.08829/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 54 references that are in the map.
- First posted on arXiv 12 Apr 2024.

## Builds on (most cited first, 22 of 22)

- [Self-Attentive Sequential Recommendation](https://mlsanity.com/paper/1808.09781/) (2018)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [Self-supervised Graph Learning for Recommendation](https://mlsanity.com/paper/2010.10783/) (2020)
- [Bias and Debias in Recommender System: A Survey and Future Directions](https://mlsanity.com/paper/2010.03240/) (2020)
- [RecBole: Towards a Unified, Comprehensive and Efficient Framework for Recommendation Algorithms](https://mlsanity.com/paper/2011.01731/) (2020)
- [How Algorithmic Confounding in Recommendation Systems Increases Homogeneity and Decreases Utility](https://mlsanity.com/paper/1710.11214/) (2017)
- [Disentangled Graph Collaborative Filtering](https://mlsanity.com/paper/2007.01764/) (2020)
- [Learning Disentangled Representations for Recommendation](https://mlsanity.com/paper/1910.14238/) (2019)
- [Embarrassingly Shallow Autoencoders for Sparse Data](https://mlsanity.com/paper/1905.03375/) (2019)
- [SimpleX: A Simple and Strong Baseline for Collaborative Filtering](https://mlsanity.com/paper/2109.12613/) (2021)
- [RecVAE: a New Variational Autoencoder for Top-N Recommendations with Implicit Feedback](https://mlsanity.com/paper/1912.11160/) (2019)
- [Outer Product-based Neural Collaborative Filtering](https://mlsanity.com/paper/1808.03912/) (2018)
- [Spectral Collaborative Filtering](https://mlsanity.com/paper/1808.10523/) (2018)
- [AutoDenoise: Automatic Data Instance Denoising for Recommendations](https://mlsanity.com/paper/2303.06611/) (2023)
- [Efficient Bi-Level Optimization for Recommendation Denoising](https://mlsanity.com/paper/2210.10321/) (2022)
- [Automated Data Denoising for Recommendation](https://mlsanity.com/paper/2305.07070/) (2023)
- [On the Generalizability and Predictability of Recommender Systems](https://mlsanity.com/paper/2206.11886/) (2022)
- [Predictability limit of partially observed systems](https://mlsanity.com/paper/2001.06547/) (2020)
- [Noise Contrastive Estimation for Scalable Linear Models for One-Class Collaborative Filtering](https://mlsanity.com/paper/1811.00697/) (2018)

## Abstract (arXiv)

Recommender Systems (RS) shape the filtering and curation of online content, yet we have limited understanding of how predictable their recommendation outputs are. We propose data-driven metrics that quantify the predictability of recommendation datasets by measuring the structural complexity of the user-item interaction matrix. High complexity indicates intricate interaction patterns that are harder to predict; low complexity indicates simpler, more predictable structures. We operationalize structural complexity via data perturbations, using singular value decomposition (SVD) to assess how stable the latent structure remains under perturbations. Our hypothesis is that random perturbations minimally affect highly organized data, but cause substantial structural disruption in intrinsically complex data. By analyzing prediction errors on perturbed interactions, we derive metrics that quantify this sensitivity at both the dataset and the interaction levels, yielding a principled measure of inherent predictability. Experiments on real-world datasets show that our structural complexity metrics correlate with the performance of state-of-the-art recommendation algorithms. We also demonstrate structure-aware data selection: in low-data settings, models trained on a carefully chosen subset of interactions with low structural perturbation error consistently outperform models trained on the full dataset. Thus, structural complexity serves both as a precise diagnostic of dataset complexity and as a principled foundation for efficient, data-centric training of RS.