Relative Pairwise Relationship Constrained Non-Negative Matrix Factorisation

Shuai Jiang, Kan Li, Richard Yi Da XuIEEE TKDE 2018 · DOI · OpenReview

TL;DR

This paper introduces RPR-NMF, a novel Non-negative Matrix Factorization (NMF) method that incorporates pairwise relationships between data points as constraints. By penalizing deviations from desired relative distances, RPR-NMF achieves more accurate factorizations and better performance in tasks like image clustering and recommender systems compared to existing NMF variants.

What Problem Does This Paper Address?

Non-negative Matrix Factorization (NMF) is a powerful technique for dimensionality reduction and feature extraction, widely used in areas like image analysis and recommender systems. However, standard NMF and many of its extensions primarily focus on the individual properties of the factorized matrices (e.g., non-negativity, sparsity, smoothness). They often overlook the crucial relative relationships between different data points or features. For instance, in a recommender system, if "Star Wars" and "Star Trek" are both sci-fi movies, their feature representations after factorization should reflect this similarity, ideally being closer to each other than to a romance movie like "Titanic." Existing methods like Graph Regularized NMF (GNMF) and Label Constrained NMF (LCNMF) attempt to address this but have limitations: GNMF's similarity constraints can be violated by the factorization process, and LCNMF's strict label-based constraints are often too restrictive. This paper aims to bridge this gap by proposing a flexible and effective way to enforce these relative pairwise relationships.

Methods

The core contribution is the Relative Pairwise Relationship constrained Non-negative Matrix Factorisation (RPR-NMF) algorithm. Instead of imposing constraints on individual vectors, RPR-NMF uses triplet-based penalties to enforce relative relationships. A triplet $(q, r, s)$ might specify that the distance between vector $q$ and $r$ should be less than the distance between vector $q$ and $s$.

The paper explores two common distance measures:

  • Squared Euclidean Distance: Penalties are formulated using natural exponential functions.
  • Symmetric Divergence (KL-Divergence): Penalties are formulated using hinge loss functions.

The authors adapt the well-known multiplicative update rules for NMF to accommodate these new penalties. To handle the complexity of proving convergence with these non-convex penalties, they employ reasonable approximations and provide theoretical convergence proofs for both distance measures. The algorithm is designed to work on both factorized matrices (W and H), offering more flexibility than previous methods.

Datasets

The paper evaluates RPR-NMF on a variety of datasets:

  • Synthetic Datasets: Used to study the influence of the number of constraints and the size of the factorizing matrix on performance.
  • AT&T ORL Database: A standard dataset for image clustering, containing images of faces with variations in lighting, expression, and pose.
  • CMU PIE Database: Another benchmark dataset for face recognition, known for its extensive variations in pose and illumination.
  • Movielens 1M Dataset: A widely used dataset for recommender systems, containing user ratings for movies.

The authors also provide algorithms (Algorithm 3 and 4) to convert pairwise relationship constraints into the formats required by GNMF and LCNMF, enabling a fair comparison.

Key Insights and Ideas

  • Relative Relationships Matter: The paper strongly emphasizes that enforcing relative distances between data points (e.g., "A is closer to B than to C") is crucial for better factorization, especially in domains like recommender systems where human intuition about similarity is important.
  • Triplet Constraints are Flexible: Using triplets to define relative distances offers a more nuanced and flexible way to capture relationships compared to absolute similarity measures or strict labels.
  • Approximations for Convergence: The authors demonstrate that practical approximations can be used to derive update rules and prove convergence for complex penalty functions, making the algorithm computationally feasible.
  • RPR-NMF Outperforms Baselines on Constraints: A key finding is that RPR-NMF is significantly better at satisfying the imposed pairwise constraints, especially when these constraints form chains, a scenario where GNMF and LCNMF struggle.

Key Results

  • Improved Accuracy and Constraint Satisfaction: RPR-NMF consistently achieved lower Mean Squared Loss (MSL) / Mean Divergence (MD) and significantly higher Constraint Satisfied Rate (CSR) compared to NMF, GNMF, and LCNMF across various experiments. For example, in synthetic experiments, RPR-NMF (Divergence) achieved the highest CSR (average 99.11%), while NMF, GNMF, and LCNMF achieved 80.16%, 64.10%, and 16.14% respectively.
  • Competitive Performance in Applications:
    • Image Clustering: RPR-NMF achieved the best average ACC (85.78%) and NMI (82.33%) on the AT&T ORL dataset, outperforming other methods.
  • Recommender Systems: On the Movielens 1M dataset, RPR-NMF achieved competitive RMSE and the highest F1 score, indicating better recommendation accuracy.
  • Robustness to Parameters: The paper notes that RPR-NMF (Euclidean version) shows some sensitivity to parameters, but the Divergence version remains stable, suggesting it's less sensitive and easier to tune.
  • Computational Efficiency: The complexity analysis indicates that RPR-NMF does not significantly increase processing time compared to standard NMF.

Limitations and Future Work

  • Approximation in Convergence Proof: While practically verified, the convergence proofs rely on approximations for the penalty terms. The paper acknowledges this and states the approximations are "reasonable and practical."
  • Parameter Tuning: While the Divergence version is noted as stable, the Euclidean version shows some parameter sensitivity, requiring careful selection for optimal performance.
  • Future Work: The paper doesn't explicitly detail future work, but the success in handling chained constraints suggests exploring more complex relational structures and applying RPR-NMF to a wider range of data modalities and applications. The authors also mention that converting stronger constraints (like labels) to weaker ones (like RPRs) can lead to information loss, hinting at potential research in bidirectional conversion or unified frameworks.

Summary updated

Abstract

Non-negative Matrix Factorisation (NMF) has been extensively used in machine learning and data analytics applications. Most existing variations of NMF only consider how each row/column vector of factorised matrices should be shaped, and ignore the relationship among pairwise rows or columns. In many cases, such pairwise relationship enables better factorisation, for example, image clustering and recommender systems. In this paper, we propose an algorithm named, Relative Pairwise Relationship constrained Non-negative Matrix Factorisation (RPR-NMF), which places constraints over relative pairwise distances amongst features by imposing penalties in a triplet form. Two distance measures, squared Euclidean distance and Symmetric divergence, are used, and exponential and hinge loss penalties are adopted for the two measures, respectively. It is well known that the so-called “multiplicative update rules” result in a much faster convergence than gradient descend for matrix factorisation. However, applying such update rules to RPR-NMF and also proving its convergence is not straightforward. Thus, we use reasonable approximations to relax the complexity brought by the penalties, which are practically verified. Experiments on both synthetic datasets and real datasets demonstrate that our algorithms have advantages on gaining close approximation, satisfying a high proportion of expected constraints, and achieving superior performance compared with other algorithms.
BibTeX
@article{jiang2018relative,
  author = {Shuai Jiang and Kan Li and Richard Yi Da Xu},
  title = {{Relative Pairwise Relationship Constrained Non-Negative Matrix Factorisation}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2018},
  doi = {10.1109/tkde.2018.2859223},
}
Figure