Source-linked AI summary
Spectral Collaborative Filtering
Lei Zheng, Chun-Ta Lu, Fei Jiang, Jiawei Zhang, Philip S. Yu
TL;DR
CF-based recommender systems face cold-start difficulties when users have few interactions, while traditional approaches often fail to model indirect graph connectivity. The paper represents users and items as a bipartite graph, introduces spectral convolution, and builds SpectralCF to learn in the spectral domain. Across standard datasets, SpectralCF outperforms comparative CF-based and graph-based models and improves cold-start recommendation results.
Problem
CF-based methods struggle with cold-start users who have interacted with very few items, and traditional approaches rarely capture indirect connectivity in user-item graphs.
Method
The paper formulates user-item relationships as a bipartite graph, introduces polynomially approximated spectral convolution, and stacks the operation into the SpectralCF deep recommendation model.
Results
20.1% and 42.6% improvements over four CF-based and two graph-based models were achieved, averaging across three standard datasets for Recall@M and MAP@M, respectively.
Takeaways & Limitations
SpectralCF uses spectral-domain connectivity information to discover deeper user-item connections and alleviate the CF cold-start problem.
Takeaways & Limitations
The study focuses on implicit feedback and leaves heterogeneous graph information and item content for future work.
Abstract
from arXiv · showhide
Despite the popularity of Collaborative Filtering (CF), CF-based methods are haunted by the \textit{cold-start} problem, which has a significantly negative impact on users' experiences with Recommender Systems (RS). In this paper, to overcome the aforementioned drawback, we first formulate the relationships between users and items as a bipartite graph. Then, we propose a new spectral convolution operation directly performing in the \textit{spectral domain}, where not only the proximity information of a graph but also the connectivity information hidden in the graph are revealed. With the proposed spectral convolution operation, we build a deep recommendation model called Spectral Collaborative Filtering (SpectralCF). Benefiting from the rich information of connectivity existing in the \textit{spectral domain}, SpectralCF is capable of discovering deep connections between users and items and therefore, alleviates the \textit{cold-start} problem for CF. To the best of our knowledge, SpectralCF is the first CF-based method directly learning from the \textit{spectral domains} of user-item bipartite graphs. We apply our method on several standard datasets. It is shown that SpectralCF significantly outperforms state-of-the-art models. Code and data are available at \url{https://github.com/lzheng21/SpectralCF}.
1 INTRODUCTION
The paper addresses CF’s cold-start problem by modeling user-item relationships as a bipartite graph and learning directly in its spectral domain. SpectralCF uses spectral convolution to exploit graph connectivity and reports stronger recommendation performance than comparative models.
- CF becomes difficult when users interact with very few items and therefore share few items with others.
- A cold-start user connected through shared items can receive more reliable recommendations from items linked by multiple graph paths.In the example, i4 has two paths from u1, whereas i2 and i3 each have one path.
- Traditional CF methods often model direct user-item proximity but rarely capture indirect connectivity, such as the number of paths between users and items.
- SpectralCF introduces a spectral convolution operation that dynamically amplifies or attenuates frequency components, then stacks these operations into a deep recommendation model.
- The paper presents SpectralCF as the first CF-based method directly learning from the spectral domains of user-item bipartite graphs.
2 DEFINITIONS AND PRELIMINARIES
The paper formalizes recommendation with implicit feedback using user-item bipartite graphs, adjacency and Laplacian matrices, and graph Fourier transforms. It defines recommendation as ranking unobserved items for each user.
- A bipartite user-item graph contains disjoint user and item vertex sets, with edges representing observed training interactions.
- The graph’s adjacency matrix is defined for the bipartite graph as an N × N matrix, and its random-walk Laplacian is L = I − D^-1A.
- Graph Fourier transformation maps graph signals into the spectral domain using Laplacian eigenvectors, with inverse transformation returning them to the original domain.
- The implicit feedback setting records whether users viewed, liked, or clicked items rather than explicit ratings.
- For each user, the recommendation task ranks items not yet included among that user’s observed positive interactions.
3 PROPOSED MODEL
SpectralCF performs collaborative filtering in the spectral domain by applying spectral convolution to graph signals on a user-item graph. Polynomial approximation reduces filter complexity, while multi-channel, multi-layer propagation produces vector representations for users and items that are trained with pairwise ranking loss.
- 3.1 Graph Fourier Transform: Graph Fourier transform represents graph signals using eigenvectors of the graph Laplacian as a spectral-domain basis.The graph signal is transformed into and reconstructed from spectral coordinates using the eigenvector matrix U.
- 3.2 Spectral Convolution: The spectral convolution filter dynamically adjusts the contribution of each frequency component to produce new user and item graph signals.The filter is parameterized by spectral quantities associated with the Laplacian eigenvalues, and the eigenvector matrix performs the inverse transform.
- 3.3 Polynomial Approximation: The unconstrained spectral filter has O(N) learning complexity, and its scalar outputs are insufficient for modeling deep user-item connections.The paper addresses these two limitations through polynomial approximation and multi-dimensional graph signals with multiple filters.
- 3.3 Polynomial Approximation: Polynomial approximation makes filter complexity O(P), independent of the number of graph vertices, with polynomial order P limited to 1 to avoid over-fitting.The paper establishes that the finite-order polynomial filter family equals the original spectral filter family before using a truncated approximation.
- 3.3 Polynomial Approximation: The final convolution uses C input channels and F filters to produce F-dimensional user and item outputs, implemented as the propagation rule of SpectralCF.The resulting operation is a generalization of the single-channel form and is parameterized by U, Λ, and Θ′.
- 3.4 Multi-layer Model: SpectralCF stacks convolution layers, concatenates representations from all layers, and trains them with Bayesian Personalized Ranking on observed-versus-unobserved item triples.The model initializes user and item vectors, propagates them through K layers, forms final latent factors, and optimizes the pairwise preference objective.
4 EXPERIMENTS
The experiments evaluate SpectralCF against CF-based and graph-based models across three datasets, examining recommendation quality, hyper-parameters, and cold-start performance. SpectralCF consistently achieves stronger results, including under sparse user histories.
- Experimental setup: Experiments compare SpectralCF with six state-of-the-art models across three publicly available datasets.The baselines include four CF-based methods and two graph-based methods.
- Evaluation: Recall@M and MAP@M evaluate top-M retrieval and ranking performance, respectively.Recall@M measures the fraction of relevant items retrieved, while MAP@M evaluates ranking quality.
- Hyper-parameter analysis: K=3 gives SpectralCF its best Recall@20 and MAP@20 performance on the MovieLens-1M validation set.The tested values of K range from 1 to 5.
- Overall findings: Performance declines as datasets become sparser, but SpectralCF remains ahead of all comparative models.The authors attribute its advantage to learning connectivity information in the spectral domain.
- Cold-start evaluation: SpectralCF improves over BPR by 36.8% in Recall@20 and 33.8% in MAP@20 for cold-start users.The comparison varies each user’s associated training items from one to five in MovieLens-1M.
5 RELATED WORKS
Related work spans deep-learning and graph-based recommender systems, while SpectralCF differs by learning latent user and item factors directly from spectral domains of user-item bipartite graphs.
- Distinction from prior work: SpectralCF is presented as distinct from prior approaches because it directly learns latent factors of users and items from user-item bipartite graph spectral domains.
- Deep learning based RS: Deep-learning recommender systems include RBM-based user modeling, generative-discriminative models, and hybrid CNN/DBN approaches for learning item representations.
- Graph-based RS: Graph-based recommender systems model document recommendation, check-in behavior, personalized tags, graph structure, and heterogeneous graph information.
- Scope: The paper focuses on implicit feedback and leaves heterogeneous graph information and item content for future work.
6 CONCLUSIONS
SpectralCF uses spectral convolution to learn user-item latent factors from connectivity information in bipartite graphs, targeting cold-start recommendation. It outperforms comparison models and improves results under sparse interactions.
- SpectralCF directly learns latent user and item factors from spectral-domain connectivity using a new spectral convolution operation.
- 20.1% and 42.6% improvements over four CF-based and two graph-based models averaged across three datasets were achieved in Recall@M and MAP@M, respectively.
- 36.8% and 33.8% average improvements over BPR were obtained for cold-start users in Recall@20 and MAP@20, respectively.
- The experiments validated that SpectralCF can effectively ameliorate the cold-start problem.