  Analytics over social graphs allows to extract valuable knowledge and
insights for many fields like community detection, fraud detection, and
interest mining. In practice, decentralized social graphs frequently arise,
where the social graph is not available to a single entity and is decentralized
among a large number of users, each holding only a limited local view about the
whole graph. Collecting the local views for analytics of decentralized social
graphs raises critical privacy concerns, as they encode private information
about the social interactions among individuals. In this paper, we design,
implement, and evaluate PrivGED, a new system aimed at privacy-preserving
analytics over decentralized social graphs. PrivGED focuses on the support for
eigendecomposition, one popular and fundamental graph analytics task producing
eigenvalues/eigenvectors over the adjacency matrix of a social graph and
benefits various practical applications. PrivGED is built from a delicate
synergy of insights on graph analytics, lightweight cryptography, and
differential privacy, allowing users to securely contribute their local views
on a decentralized social graph for a cloud-based eigendecomposition analytics
service while gaining strong privacy protection. Extensive experiments over
real-world social graph datasets demonstrate that PrivGED achieves accuracy
comparable to the plaintext domain, with practically affordable performance
superior to prior art.
