Convex Collective Matrix Factorization

Guillaume Bouchard, Dawei Yin, Shengbo GuoAISTATS 2013 · OpenReview

Abstract

In many applications, multiple interlinked sources of data are available and they cannot be represented by a single adjacency matrix, to which large scale factorization method could be applied. Collective matrix factorization is a simple yet powerful approach to jointly factorize multiple matrices, each of which represents a relation between two entity types. Existing algorithms to estimate parameters of collective matrix factorization models are based on non-convex formulations of the problem; in this paper, a convex formulation of this approach is proposed. This enables the derivation of large scale algorithms to estimate the parameters, including an iterative eigenvalue thresholding algorithm. Numerical experiments illustrate the benefits of this new approach.

Introduction

In modern data science, we rarely have just one table. We often have multiple "views" or relations: users rating movies, users having demographic profiles, and movies belonging to genres. Collective Matrix Factorization (CMF) aims to learn latent signatures for these entities (users, movies, genres) by factorizing all these matrices simultaneously, sharing information across them.

However, traditional CMF methods are non-convex, meaning algorithms often get stuck in local minima, making them sensitive to initialization and hard to scale reliably. While some researchers use tensors to represent this data, tensors are notoriously difficult to approximate and relax into convex forms. This paper introduces a framework for jointly factorizing multiple interlinked datasets while guaranteeing a global optimum.

Methods: The Collective Nuclear Norm

The authors' primary contribution is the Collective Nuclear Norm ($\|X\|_\sharp$). By defining this novel norm based on a large symmetric block matrix, they transform a traditionally non-convex problem into a convex one.

The Block Matrix Trick

Instead of looking at each relation matrix in isolation, the authors arrange all available relations into a single, large, symmetric block matrix. If you have three entity types ($E_1, E_2, E_3$) forming a loop of relations, the block matrix places these relations in specific "slots" while leaving unknown or non-existent relations as zeros.

Mapping relational structures to a symmetric block matrix.

The standard nuclear norm of a single matrix is the sum of its singular values. The authors show that their collective nuclear norm is equivalent to the sum of the absolute eigenvalues of this massive block matrix. This naturally handles "loopy" relational structures (e.g., User-Movie, Movie-Genre, Genre-User) that simpler concatenation methods miss.

Optimization Algorithms

The convex formulation enables the use of highly efficient, scalable algorithms:

  • Singular Value Thresholding (SVT): A proximal gradient method that iteratively performs an eigenvalue decomposition and "shrinks" the values. This is the paper's preferred scalable approach.
  • Stochastic Gradient Descent (SGD): An alternative based on a decomposition formulation of the norm, useful for very large, sparse observations.

Key Insights and Results

The authors evaluated their approach on both simulated data and real-world benchmarks, including MovieLens 1M (6,000 users, 4,000 movies, demographics, and genres) and Flickr (users, tags, comments, items).

Convexity and Stability

Because the problem is convex, the choice of starting parameters doesn't matter. In experiments, the SGD-based version became much less sensitive to initialization as the latent dimension increased, eventually converging to the same global optimum as the SVT method.

Efficiency of SVT

One of the most striking findings was that the SVT algorithm outperformed optimized C-code SGD by orders of magnitude in terms of convergence speed, despite SVT being implemented in unoptimized Matlab.

Convergence speed comparison of SVT vs SGD on MovieLens 1M.

Predictive Performance

  • Lower Error: In simulations, the collective approach reduced error significantly compared to factorizing each matrix independently (e.g., an error of 0.673 vs 1.21 for rank-2 data).
  • MovieLens Performance: Convex CMF (CCMF) consistently achieved lower Root Mean Square Error (RMSE) than standard Probabilistic Matrix Factorization (PMF). For example, on a 50% training split, CCMF achieved an RMSE of 1.0320 compared to PMF's 1.0415.

Conclusion

Convex Collective Matrix Factorization offers a principled and scalable way to handle complex relational data. By leveraging the collective nuclear norm, it avoids the pitfalls of local minima inherent in non-convex methods. The efficiency of the SVT algorithm makes this approach viable for large-scale knowledge graphs where most entries are missing, paving the way for more robust multi-view learning.

Summary updated

Abstract

In many applications, multiple interlinked sources of data are available and they cannot be represented by a single adjacency matrix, to which large scale factorization method could be applied. Collective matrix factorization is a simple yet powerful approach to jointly factorize multiple matrices, each of which represents a relation between two entity types. Existing algorithms to estimate parameters of collective matrix factorization models are based on non-convex formulations of the problem; in this paper, a convex formulation of this approach is proposed. This enables the derivation of large scale algorithms to estimate the parameters, including an iterative eigenvalue thresholding algorithm. Numerical experiments illustrate the benefits of this new approach.
BibTeX
@inproceedings{bouchard2013convex,
  author = {Guillaume Bouchard and Dawei Yin and Shengbo Guo},
  title = {{Convex Collective Matrix Factorization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2013},
  url = {https://openreview.net/forum?id=3SLNVDyLoT},
}
Figure