TarDPR: Redefining Friend Recommendations via Sparsity-Aware Dot Product Representations

TL;DR

Recommending "who to follow" or "who to friend" is a cornerstone of modern Online Social Networks (OSNs). While local heuristics like "Common Friends" are simple, they often fail to capture the global structure of the network. This paper introduces Targeted Dot Product Representation (TarDPR), a framework that maps users into a vector space where friendship is predicted by dot products. By adding a clever sparsity constraint, TarDPR filters out noise and outperforms traditional methods by up to 15% on real-world datasets like Facebook and Foursquare.

Problem & Motivation: The Global vs. Local Gap

Most recommendation engines rely on local topology—for instance, if Alice and Bob have ten friends in common, they should probably be friends. However, these methods lack a systematic quantification of the entire network. On the other hand, early Dot Product Representation (DPR) models attempted to map the whole graph but suffered from a "hallucination" problem: they would predict too many connections in sparse areas where no relationship was likely to form.

The authors' core insight is that a recommendation model must not only be consistent with existing links but also disciplined about creating new ones. In social networks, the connections are naturally sparse; the model should respect this physical reality.

Methodology: The Fusion of Latent Space and Sparsity

TarDPR transforms the friendship graph into a matrix completion-style problem. Each user $i$ is assigned a vector ${\mathbf{x}}_i\in {\mathbb{R}}^d$. The goal is to make the dot product $⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$ close to $1$ if a link exists, and close to $0$ if it doesn't.

The mathematical "secret sauce" is the introduction of an $L_1$-norm penalty specifically on the missing links (the complement set $\bar{\Omega }$):

${\min }_{\mathbf{X}}\Vert \mathbf{A}-({\mathbf{X}}^T\mathbf{X}){|}_{\Omega }{\Vert }_F^2+\lambda |({\mathbf{X}}^T\mathbf{X}){|}_{\bar{\Omega }}{|}_1$

The Algorithm

To solve this efficiently at scale, the authors employ the Alternating Direction Method of Multipliers (ADMM).

1. Sparsity Step: It uses a soft-thresholding operator to enforce sparsity on the predicted new links.
2. Representation Step: It utilizes an iterative eigenvalue method to update the user feature vectors.

Note: The representation maps a weighted graph into a point cloud of feature vectors where affiliation is governed by angular similarity.

Experiments & Results: Crushing the Baselines

The authors tested TarDPR against classic measures like Jaccard’s Coefficient, Common Friends, and Friends-Measure on Facebook (60k nodes) and Foursquare (45k nodes).

Key Findings:

• Scale of Recovery: On Facebook, TarDPR recovered 64% of hidden links while only suggesting a tiny fraction (0.1%) of the total possible connections in the network.
• Feature Synergies: One of the most interesting results is that TarDPR is "orthogonal" to traditional features. When you combine TarDPR with "Common Friends," the performance jumps significantly—suggesting that TarDPR captures global structural features that local heuristics miss.

The ROC-like curve above shows TarDPR (d=800) maintaining a higher recovery rate across various filling rates compared to Jaccard and Common Friends.

Critical Analysis & Takeaways

The beauty of TarDPR lies in its flexibility. It isn't just restricted to friendship links; it can incorporate geographical check-ins or message frequency into the adjacency matrix $\mathbf{A}$ to learn even richer user embeddings.

Limitations:

• The choice of dimension $d$ is tricky. On Facebook, higher $d$ was better, but on Foursquare, lower $d$ performed better—indicating that the "intrinsic dimensionality" of different social platforms varies wildly.
• As an ADMM-based iterative method, while efficient, it may still face scalability challenges compared to modern decentralized Graph Neural Networks on billion-node scales.

Future Outlook: This work paved the way for modern "embedding-based" recommendation systems. It proved that link prediction is not just about local counting, but about finding the right low-rank manifold that describes human social behavior.