PGPI: Precision Profile Inference with Only a Fraction of the Social Graph

TL;DR

Inferring private user attributes (e.g., gender, occupation) in social networks usually requires a "god-view" of the entire graph. PGPI (Partial Graph Profile Inference) breaks this requirement. By using a "lazy" algorithm that focuses on local neighborhoods and rich interaction data (likes, views, groups), it achieves >90% accuracy for key attributes while visiting only a small fraction of the network.

The "Full Graph" Fallacy

In academic research, we often use static datasets where the entire social graph is available. In the real world, this is a fantasy. APIs (like Facebook's) rate-limit access, and the graph is too massive and dynamic to keep fully updated.

Current state-of-the-art methods like Label Propagation (LP) or Graphical Models fail here because:

1. They require global iterations to converge.
2. They rely heavily on the "homophily" of links (friends are similar) but ignore "rich information" like shared interests and content consumption.

Methodology: The Power of Local Insight

The authors propose a hybrid approach that balances social structure and behavioral similarity.

1. PGPI-N (Link-based)

Instead of global propagation, PGPI-N performs a localized Breadth-First Search (BFS). It weights a neighbor's influence based on:

• Physical Distance: Closer neighbors influence more ($1/dist$).
• Attribute Similarity: Neighbors who already share known attributes are given higher weights ($W_{i,j}$).

2. PGPI-G (Interaction-based)

This component targets the "Common Interest" signal. It looks at:

• Common Likes & Views: Digital footprints on publications.
• Group Popularity: Attributes that are dominant within a specific shared group.

The algorithm uses a ratioFacts parameter to balance the budget between link-based (N) and group-based (G) discovery.

Experiments: Superiority in Sparsity

The researchers tested PGPI against 11,247 Facebook users. The core metric was PAC (Product of Accuracy and Coverage)—essentially, how often is the model right, and how often does it actually dare to make a prediction?

Key Findings:

• Efficiency: PGPI reached its peak performance with only ~400 "facts" (nodes/groups), while traditional algorithms essentially crashed or stayed at baseline accuracy when denied the full graph.
• Attribute Accuracy: Gender (94.6%) and Status (90.9%) were highly predictable even with partial data.
• The "Lazy" Advantage: Because it doesn't require a training phase, it avoids the "overfitting to a specific graph snapshot" problem that plagues Naïve Bayes approaches.

Table 1: Detailed performance across attributes. Note that PGPI remains robust across various categories like 'Major' and 'Residence' where baselines struggle.

Critical Insight: Why Does This Work?

The effectiveness of PGPI lies in its Inductive Bias. It assumes that in an era of strict privacy settings, "who you follow" or "what you like" is actually a stronger signal than "who your friends are." By weighting influencers by distance and similarity, the model filters out the "noise" of casual acquaintances that usually muddies global propagation models.

Conclusion & Limitations

PGPI proves that you don't need to see the whole world to know who someone is. From a security perspective, this is a warning: even if you hide your friend list, your public group memberships and "likes" are enough to reconstruct 90% of your profile.

Limitations: The algorithm's reliance on the maxDistance parameter means it might struggle in extremely fragmented networks where the "Shortest Path" isn't representative of actual social influence. Future iterations using non-linear similarity kernels could further enhance its robustness.