Symmetric Non-negative Latent Factor Models for Undirected Large Networks

Xin Luo, Mingsheng ShangIJCAI 2017 · DOI

TL;DR

This paper introduces Symmetric Non-negative Latent Factor (SNLF) models to address the limitations of existing Non-negative Latent Factor (NLF) models when applied to undirected networks. By enforcing symmetry, SNLF models better capture the inherent structure of undirected data while maintaining efficiency and accuracy in tasks like missing data estimation.

What Problem Does This Paper Address?

Many real-world networks, such as social networks, e-commerce platforms, and biological interaction networks, are undirected. These networks are often represented by symmetric matrices, meaning the relationship from entity A to entity B is the same as from B to A. However, traditional Non-negative Latent Factor (NLF) models, while effective for asymmetric networks, struggle to accurately represent this inherent symmetry. This limitation can lead to suboptimal performance when analyzing undirected data. The paper aims to bridge this gap by developing NLF models that explicitly account for the symmetry of undirected networks, leading to more accurate and efficient analysis.

Methods

The core contribution of this paper is the development of Symmetric Non-negative Latent Factor (SNLF) models. The authors analyze the NLF extraction process for both asymmetric and symmetric matrices. They propose a novel approach that enforces symmetry by using a single latent factor matrix (A) to reconstruct the original symmetric matrix (R) through the operation R ≈ A * A^T. This contrasts with standard NLF models that might use two separate matrices (P and Q) for reconstruction (R ≈ P * Q^T), which can lead to asymmetry.

The paper also introduces a Biased SNLF (BSNLF) model by incorporating linear biases into the SNLF framework. This is achieved by extending the objective function to include bias terms for each entity.

The update rules for these models are derived using an additive gradient descent (AGD) approach, leading to multiplicative update rules that are efficient and maintain the non-negativity constraint. A key theoretical insight is the connection between SNLF and NLF: an NLF model can achieve symmetric results if initialized with identical latent factor matrices (P=Q).

Datasets

The experiments were conducted on four real-world datasets, all of which are Symmetric, High-Dimensional, and Sparse (SHiDS) matrices:

  • D1: Protein interactome in Pseudomonas Aeruginosa PAO1.
  • D2: Protein interactome in Arabidopsis Thaliana.
  • D3: Temperature data of a steel cylinder.
  • D4: Vibration stiffness data of a piece of special material.

Datasets D1 and D2 are from the STRING database, while D3 and D4 are from the University of Florida sparse matrix collection.

Key Insights and Ideas

  • Symmetry Matters: Explicitly modeling the symmetry of undirected networks with SNLF models leads to a more rigorous representation of the underlying data structure compared to asymmetric NLF models.
  • Symmetry vs. Accuracy Trade-off (Data Dependent): While SNLF models inherently capture symmetry, their prediction accuracy for missing data can be data-dependent. On some datasets, asymmetric NLF models might achieve slightly better accuracy, suggesting that perfect symmetry doesn't always guarantee superior predictive performance.
  • Ensemble Effect of Asymmetric NLF: The paper hypothesizes that asymmetric NLF models might achieve better accuracy on certain datasets due to an "ensemble effect" where two distinct latent factor matrices (P and Q) can be seen as representing different hypotheses, potentially capturing numerical characteristics more effectively.
  • Computational Efficiency: SNLF and BSNLF models demonstrate significantly higher computational efficiency than their asymmetric counterparts and SNMF, especially as the latent dimension increases. This is attributed to training a single latent factor matrix instead of two.
  • Biases are Data-Dependent: The benefit of incorporating linear biases (BSNLF) is also data-dependent. On some datasets, biases improved accuracy, while on others, they led to a slight decrease.

Key Results

  • Symmetry Validation: Figures 1(d) and 1(e) clearly show that SNLF (M4) and BSNLF (M5) models accurately capture the symmetry of the target network, with data points clustering along the x=y line in low-rank approximation plots. Asymmetric models (M1, M2) failed to do so.
  • Missing Data Estimation:
    • On datasets D2-D4, SNLF (M4) and BSNLF (M5) consistently outperformed asymmetric NLF models (M1, M2) in terms of RMSE (lower is better). For example, on D2 with d=80, M4 achieved 1.73% better accuracy than M1, and M5 achieved 1.64% better than M2.
  • On dataset D1, asymmetric models (M1, M2) showed slightly better performance than their symmetric counterparts (M4, M5).
  • SNMF (M6) consistently performed worse than all other models across all datasets.
  • Computational Efficiency: Figure 4 shows that SNLF (M4) and BSNLF (M5) are significantly faster than M1, M3, and M6. M4 is approximately twice as fast as M1 and M3, and M5 is also considerably faster than M2. M6 (SNMF) was the slowest due to its need to process full matrices.

Limitations and Future Work

  • Strict Symmetry Constraint: The authors acknowledge that the strict constraint R = A * A^T might be too restrictive. Future work could explore decomposing symmetric matrices into multiple LF matrices while still maintaining symmetry.
  • Data Dependency of Biases: The effectiveness of linear biases is shown to be data-dependent, suggesting further investigation into when and how to best incorporate them.
  • Industrial Applications: The paper suggests exploring a wider range of industrial applications for SNLF models.
  • Model Structure and Training: Improving the model structure and developing constrained training processes are identified as avenues for further boosting performance.
  • Investigating SNMF Limitations: The paper notes that SNMF is not directly designed for SHiDS matrices and requires prefilling missing data, which limits its applicability and performance in this context.

Summary updated

BibTeX
@inproceedings{luo2017symmetric,
  author = {Xin Luo and Mingsheng Shang},
  title = {{Symmetric Non-negative Latent Factor Models for Undirected Large Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/339},
}
Figure