Collaborative Filtering with Generalized Laplacian Constraint via Overlapping Decomposition

Qing Zhang, Houfeng Wang

Abstract

Traditional Matrix Factorization (MF) techniques in Collaborative Filtering often struggle to capture the complex, overlapping community structures inherent in user-item interactions. This paper introduces Multi-facet Hidden Graph Matrix Factorization (MHGMF), a framework that generalizes the Laplacian constraint to automatically discover overlapping latent structures. By decomposing multifaceted user preferences into multiple non-overlapping "views" and employing diversity-promoting regularization, MHGMF significantly improves recommendation accuracy across various real-world datasets.

Introduction

Collaborative Filtering (CF) remains a cornerstone of modern recommendation systems. Standard Matrix Factorization (MF) models represent users and items in a low-dimensional latent space, assuming that a small number of factors can explain observed ratings. However, these models often treat latent factors as unstructured or assume users belong to single, distinct groups.

In reality, users exhibit overlapping interests, participating in multiple communities simultaneously (e.g., a user might be both a jazz enthusiast and a fitness buff). Existing attempts to model these structures typically rely on pre-defined social networks or enforce rigid, non-overlapping constraints. The challenge addressed here is the automatic discovery of these overlapping latent structures directly from rating data during optimization.

Methodology: Multi-facet Hidden Graph Matrix Factorization (MHGMF)

The core innovation of MHGMF is the generalization of the Laplacian constraint. While traditional Laplacian regularization enforces a simple block-diagonal structure (representing distinct clusters), MHGMF utilizes an Overlapping Decomposition strategy.

Overlapping Decomposition

Instead of a single complex graph, the model decomposes user relations into multiple "multi-facet graphs." Each graph represents a specific, non-overlapping "view" of user interests. The combination of these views captures the true overlapping nature of real-world behavior.

Conceptual diagram of decomposing overlapping user interests into multiple non-overlapping hidden graph facets.

Diversity and Sparsity

To ensure these facets capture unique information, the authors employ the Hilbert-Schmidt Independence Criterion (HSIC) as a penalty term, forcing the model to find non-redundant views. Additionally, $L_{2,1}$-Norm Regularization is used to encourage group sparsity, allowing the model to adaptively select relevant latent factors for each interest group.

Optimization

The model performs joint optimization of user/item embeddings and hidden group structures. This process occurs on a Stiefel manifold, a mathematical space that preserves the necessary constraints for the Laplacian decomposition during learning.

Experimental Evaluation

The MHGMF framework was evaluated on three diverse datasets:

  • LastFM: Music artist recommendations (binary).
  • Delicious: Social bookmarking (binary).
  • Epinions: Product reviews (integer ratings 1-5).

These datasets vary in sparsity, providing a robust test for the model's ability to handle missing data.

Results and Discussion

MHGMF consistently outperformed state-of-the-art baselines, including Probabilistic Matrix Factorization (PMF) and Graph-regularized Sparse Matrix Factorization (GSMF).

Accuracy and Recall

As shown in Figure 4, MHGMF achieves superior Recall on the LastFM dataset compared to other methods. The performance gap is particularly evident as the number of recommended items increases. Similar trends were observed in the Delicious and Epinions datasets, where MHGMF achieved lower Root Mean Square Error (RMSE) than traditional models.

Recall performance comparison on the LastFM dataset, showing MHGMF outperforming various baseline models.

Robustness to Sparsity

The structured group prior introduced by the multi-facet graphs proved particularly effective in sparse data scenarios. By leveraging inferred community structures, the model can make more accurate predictions even for users with limited interaction history (the "cold-start" problem).

Conclusion

MHGMF offers a powerful approach to modeling the multifaceted nature of user preferences without requiring external metadata. By proving a theoretical link between the Laplacian constraint and Normalized Cut (Ncut) problems, the authors provide a solid foundation for spectral clustering within MF. Future work includes the integration of explicit social graphs and automated determination of the optimal number of facets.

Summary updated

Abstract

Real-world data are seldom unstructured, yet traditional Matrix Factorization (MF) models, as one of the most powerful collaborative filtering approaches, generally rely on this assumption to recover the low-rank structures for recommendation. However, few of them are able to explicitly consider structured constraint with the underlying low-rank assumption to model complex user interests. To solve this problem, we propose a unified MF framework with generalized Laplacian constraint for collaborative filtering. We investigate the connection between the recently proposed Laplacian constraint and the classical normalized cut problem, and make it possible to extend the original non-overlapping prior, to capture the overlapping case via learning the decomposed multi-facet graphs. Experiments on realworld datasets demonstrate the effectiveness of the proposed method.
BibTeX
@inproceedings{zhang2016collaborative,
  author = {Qing Zhang and Houfeng Wang},
  title = {{Collaborative Filtering with Generalized Laplacian Constraint via Overlapping Decomposition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure