FM+CC: Boosting Friend Recommendation by Merging K-Means with Factorization Machines

Executive Summary

TL;DR: This paper tackles the chronic problem of data sparsity in Social Network Services (SNS) by proposing a dual-stage model. By first clustering users via K-means and then feeding those cluster assignments into a Factorization Machine (FM), the authors created a model (FM+CC) that reduces dimensionality and significantly improves recommendation accuracy. Tested on real-world Tencent Weibo data, the model achieved a remarkable 40.13% acceptance rate, proving that "pre-grouping" users is a powerful precursor to matrix decomposition.

Academic Positioning: This work sits at the intersection of classical Data Mining (Clustering) and Recommendation Systems (Factorization). It serves as a structural refinement of the original Factorization Machine proposed by Steffen Rendle, optimized for high-sparsity SNS environments.

Problem & Motivation

In modern SNS platforms like Facebook or Weibo, the "user-item" (or user-friend) matrix is notoriously sparse—often with less than 1% of entries filled. Traditional Matrix Factorization (MF) models like SVD or PMF are effective but limited in how they incorporate auxiliary information (like user age or gender).

The authors observed a trade-off:

1. Basic FM models are too simple to capture complex user profiles.
2. FM with raw User-Features (FM+UF) leads to a "dimensionality explosion," where the number of interactions ($x_i{x}_j$) becomes too large, causing over-fitting and computational bottlenecks.

Their intuition? Clustering acts as a noise filter. Instead of treating every individual user feature as a separate dimension, grouping users into "types" allows the FM to learn interactions between categories of people, which is more robust than learning interactions between individual attributes.

Methodology: The FM+CC Framework

1. Collaborative Clustering (The K-Means Stage)

The model uses K-means to partition users into $|C|$ clusters. The distance metric used is the standard Euclidean distance based on features like gender, age, and tweet frequency. $J_c(m)={\sum }_{j=1}^k{\sum }_{X_i\in C_j}{\left|X_i-Z_j\right|}^2$

2. Factorization Machine (The Interaction Stage)

The cluster ID is then fed into a 2-way FM. The core equation relies on the dot product of latent vectors $v_i$ and $v_j$ to model the interaction between the user, the potential friend (ItemUser), and the Cluster-Category: $\hat{y}(x):={\vartheta }_0+{\sum }_{i=1}^n{\vartheta }_i{x}_i+{\sum }_{i=1}^n{\sum }_{i^{\prime }=i+1}^n{x}_i{x}_{i^{\prime }}{\sum }_{f=1}^k{v}_{i,f}\cdot v_{i^{\prime },f}$

3. Optimization via MCMC

Unlike standard Stochastic Gradient Descent (SGD), which requires careful tuning of learning rates, the authors utilize Markov Chain Monte Carlo (MCMC). This approach treats parameters as random variables and samples from their posterior distribution, making it highly effective for sparse data where gradients might be noisy.

Experiments & Results

The model was validated using a 2012 Tencent Weibo dataset containing 73 million records, which was sub-sampled to 1.17M training records.

Performance Comparisons

• RMSE Reduction: The FM+CC model achieved an RMSE of 0.5015, outperforming both the Basic FM (0.5824) and the FM+User-Feature model (0.5245).
• Acceptance Rate: The most impressive leap was in the recommendation acceptance rate, which reached 40.13%, drastically higher than the 7.03% observed in the raw data.

Hyperparameter Sensitivity

The authors found that the optimal number of latent factors ($k$) was 24 and the ideal number of clusters was 16. Increasing $k$ beyond this point led to over-fitting, as the model began to "memorize" noise rather than learn generalizable social patterns.

Critical Analysis & Conclusion

Takeaway

The success of combining K-means with FM demonstrates that dimensionality compression via unsupervised learning is a viable pre-processing step for supervised recommendation tasks. It solves the "sparsity vs. feature richness" paradox by aggregating sparse individual features into dense group identities.

Limitations

• Dynamic Interests: The clustering is performed on static/semi-static features (age, gender). It does not account for the temporal evolution of user interests.
• Cold Start for Items: While it classifies users well, the model still requires some interaction history for the "ItemUser" (the person being recommended).

Future Outlook

This methodology could easily be extended to other domains, such as e-commerce or movie streaming, where users can be clustered by demographic or purchasing tiers before applying deep factorization models (like DeepFM or xDeepFM).