Abstract
Neighborhood-based collaborative filtering (CF) methods are widely used in industry due to their interpretability. However, they suffer from a fundamental mathematical limitation known as the "rating bound problem": predicted ratings are strictly bounded by the range of observed neighbor ratings. This prevents systems from accurately predicting a user's absolute favorite or least favorite items. We propose a Scalar Function Recovery (SFR) approach that treats ratings as a smooth function on an item-item similarity network. By minimizing the $l_p$-norm of the discrete second derivative, SFR identifies sparse "interest centers," enabling accurate extrapolation beyond observed bounds. Our evaluation across multiple real-world datasets shows that SFR improves rating estimation accuracy by up to 37% for items affected by the bounding problem.
Introduction: The Rating Bound Problem
In standard neighborhood-based CF, such as k-Nearest Neighbors (kNN), the predicted rating for an item is calculated as a weighted average of its neighbors' ratings. Mathematically, this implies that the prediction $\hat{r}$ is always constrained: $\min(r_{neighbors}) \le \hat{r} \le \max(r_{neighbors})$.
This constraint creates a "ceiling" for a user's favorite items and a "floor" for their most-hated ones. If a user truly loves a specific movie more than any similar movies they have rated, a kNN-based system will systematically underestimate that preference. While latent factor models can bypass this, they often lack the transparency and interpretability required for many industrial applications.
Methodology: Scalar Function Recovery (SFR)
The authors reframe the recommendation task as a signal processing problem on a graph.
The Linearity Assumption
The core hypothesis is that for the majority of items, a user's rating function $r_u(\cdot)$ is "smooth" or "linear" relative to the item-item similarity network. In graph calculus, this is expressed by the Laplacian operator (the discrete second derivative) being zero: $\nabla^2 r_u(i) = 0$. Empirical analysis of the Douban, Goodreads, and MovieLens datasets confirms this, showing that the second derivative follows an exponential decay centered at zero for the vast majority of items.
Sparse Optimization
To allow for "interest centers"—items where a user's preference deviates significantly from the neighborhood average—the authors relax the strict linearity constraint. They assume a user has only a few true sources of extreme interest. The SFR approach finds the rating distribution $\hat{R}_u$ that minimizes the $l_p$-norm (specifically $l_{1/2}$) of the second derivative: $$\hat{R}_u = \arg \min_{R_u} ||\nabla^2 R_u||_p$$ This optimization allows the model to "extrapolate" beyond observed neighbor values if it results in a simpler, sparser set of interest centers across the network.
Experimental Results
The SFR approach was tested against standard kNN and the Heat Conduction Process (HCP) using both synthetic and real-world data.
Toy Data Analysis
On a synthetic dataset designed to test extrapolation, SFR demonstrated its unique ability to "break the ceiling." As shown in the figure below, while kNN and HCP were trapped within the observed range of 4 to 7, SFR successfully recovered the extreme values of 9 and 2.
Real-World Performance
Evaluations on the MovieLens dataset focused on items where the ground truth rating fell outside the neighborhood bounds. SFR consistently achieved the lowest Root Mean Square Error (RMSE) compared to baselines.
Across all three datasets (Douban, Goodreads, MovieLens), SFR provided a significant accuracy boost, particularly for the "interest centers" that define a user's unique taste.
Conclusion
By treating collaborative filtering as a scalar function recovery problem, SFR overcomes the inherent mathematical limitations of neighborhood-based methods. It preserves the interpretability of local item relationships while gaining the ability to accurately predict extreme preferences. Future work includes exploring the relationship between different users' rating functions to improve performance in cold-start scenarios and incorporating global popularity priors.
Summary updated