FDist: Balancing Privacy and Scalability in Decentralized Friend Recommendations

TL;DR

In the era of privacy-centric decentralized social networks (DOSNs), traditional friend recommendation is a challenge. FDist solves this by using Bloom Filters for initial data probing and Decentralized Matrix Factorization to assign users low-dimensional coordinates. This allows users to estimate their mutual common friends (NCF) accurately with minimal bandwidth and no exposure of their actual friend lists.

Background: The Privacy-Scalability Paradox

Centralized giants like Facebook have the luxury of global visibility to calculate the Number of Common Friends (NCF)—the gold standard for link prediction. In a distributed setting, however, we face a paradox:

1. Privacy: Sharing a friend list with a stranger to calculate NCF is a security breach.
2. Efficiency: Using Private Set Intersection (PSI) with homomorphic encryption is too heavy for mobile/edge nodes.
3. Accuracy: Simple random sampling of social graphs often misses the sparse "friend-of-friend" connections.

Methodology: The Two-Tiered Approach

1. Privacy-Preserving Probing with Bloom Filters

To hide raw identifiers, FDist maps friend lists into a bit array (Bloom Filter). Since user IDs are hashed (SHA-1), an attacker cannot "guess" who is in the list. By exchanging these filters, nodes can sample small sets of NCF values. FDist dynamically adjusts the filter size $m$ to maintain a false positive rate $au$ below $10^{-6}$.

2. Decentralized Coordinate Optimization

To avoid the constant overhead of exchanging Bloom Filters, FDist adopts a Coordinate System. Each user $i$ is assigned a vector $\overrightarrow{u_i},\overrightarrow{v_i}$ and a set of thresholds $het{a}_i$.

The NCF value is estimated as the dot product of these vectors. Because NCF is an integer (ordinal), FDist uses a soft-margin loss function (similar to SVMs) to ensure the coordinate distance falls within the correct threshold ranges.

The optimization is performed locally using a Nonlinear Conjugate Gradient method, ensuring that each node updates its position based on its neighbors' coordinates without a central server.

Experimental Validation

The authors tested FDist on real social graphs from Facebook and Flickr.

Convergence and Accuracy

FDist converges rapidly, typically within 10 rounds, making it viable for dynamic networks where users frequently join or leave. When compared to LandmarkMDS and MatrixFac, FDist consistently showed lower Normalized Mean Absolute Error (NMAE).

Scalability

The beauty of the coordinate system is the fixed bandwidth cost. While Talash's cost grows linearly with the number of friends, FDist's transmission size remains constant at the size of the coordinate vector (around 6 dimensions in this study).

Critical Insights & Takeaways

FDist demonstrates a clever transition from measurement (Bloom Filters) to estimation (Coordinates).

• The "Why": The use of matrix factorization effectively "compresses" the global social structure into local vectors.
• Limitations: The model assumes "semi-honest" users. In a malicious environment, a "Sybil" could lie about its coordinates to manipulate recommendations.
• Future Impact: This approach is not limited to social networks; it can be applied to any decentralized system requiring discovery, such as P2P resource sharing or distributed IoT registries.

FDist proves that we don't need a "Big Brother" server to know who our friends' friends are.