PPS-POI-Rec: Bridging Social Graphs and Location Services without Sacrificing Privacy
PPS-POI-Rec: A Privacy Preserving Social Point-of-Interest Recommender System
PPS-POI-Rec is a privacy-preserving social POI recommender system that leverages both user check-in data and social graphs. It employs the Paillier cryptosystem and Yao's Garbled Circuits (YGC) to enable joint recommendation between an LBS provider and an SNS provider without either party revealing their raw private data.
TL;DR
PPS-POI-Rec is a pioneering framework that solves the tension between social-aware recommendations and data privacy. By combining Paillier Homomorphic Encryption and Yao's Garbled Circuits, it allows a Social Network Service (SNS) and a Location-Based Service (LBS) to jointly compute top-K recommendations without ever seeing each other’s private databases.
The "Data Silo" Dilemma in Social Recommendation
In the realm of Point-of-Interest (POI) recommendation, the "cold start" problem is a persistent ghost. New users with few check-ins are hard to profile. Social recommendation offers a fix by using "who you know" to guess "where you'll go."
However, there is a massive structural barrier:
- The SNS Provider (e.g., Facebook) owns the Social Graph ().
- The LBS Provider owns the Check-in Matrix ().
Both datasets are sensitive commercial assets and subject to strict privacy regulations. Prior works often assumed a trusted third party or required one party to leak data to the other. PPS-POI-Rec asks: Can we collaborate without trust?
Methodology: The Cryptographic Handshake
The authors propose a two-layered architecture that splits the workload between the mobile client and a dual-server backend (SNS + LBS).
1. Encrypted Similarity Computation
The SNS provider calculates user similarities (using metrics like Common Neighbors or Random Walk with Restart) based on the social graph. To prevent the LBS provider from seeing these weights, the SNS provider uses the Paillier cryptosystem. Because Paillier is additively homomorphic, the LBS provider can perform operations on the encrypted values to calculate recommendation scores without ever decrypting the underlying similarity score.
2. Secure Top-K Selection via Yao’s Garbled Circuits (YGC)
Computing scores is one thing; finding the "Best 5" is another. If the LBS provider simply sends the encrypted scores back to the SNS for ranking, the SNS might learn too much about user preferences. To solve this, the system uses Yao’s Garbled Circuits (YGC).
- The LBS acts as the circuit constructor.
- The SNS acts as the evaluator.
- They execute a secure comparison protocol that outputs only the final POI IDs to the user, keeping the intermediate scores hidden from both providers.
Figure 1: The dual-layer architecture of PPS-POI-Rec showing the interaction between SNS and LBS providers.
Experiments and Implementation
The system was deployed using a robust tech stack:
- Backend: Neo4j (for social graphs) and MySQL (for check-ins).
- Crypto: FasterGC implementation for the Garbled Circuits and a Java-based Paillier library.
- Real-world Data: A dataset of nearly 200,000 POIs in Suzhou, China.
The demonstration shows that the system can process requests from an Android client, perform the secure two-party computation, and return localized results (as seen in Figure 3) with practical latency.
Figure 2: The Social Graph visualization in Neo4j (left) and the resulting POI recommendations on the mobile app (right).
Critical Insights & Future Outlook
Takeaway: PPS-POI-Rec proves that the "Social + LBS" recipe can be cooked in a "Privacy-First" kitchen. The use of hybrid cryptography (Paillier for bulk math, YGC for logical comparison) is a sophisticated choice that balances computational load.
Limitations:
- Scalability: While 1,892 users are fine for a demo, YGC and Paillier incur significant overhead compared to plaintext operations. Scaling to millions of users would require optimizations like TEEs (Trusted Execution Environments) or more efficient MPC protocols.
- Network Overhead: Garbled circuits require significant bandwidth for transferring circuit tables.
Future Work: This framework opens the door for "Cross-Platform Intelligence." Imagine a world where your music streaming service and your fitness app collaborate to suggest a "Running Playlist" without either app knowing your full medical history or your entire music library. PPS-POI-Rec is a blueprint for that future.