  Graph analysts cannot directly obtain the global structure in decentralized
social networks, and analyzing such a network requires collecting local views
of the social graph from individual users. Since the edges between users may
reveal sensitive social interactions in the local view, applying differential
privacy in the data collection process is often desirable, which provides
strong and rigorous privacy guarantees. In practical decentralized social
graphs, different edges have different privacy requirements due to the distinct
sensitivity levels. However, the existing differentially private analysis of
social graphs provide the same protection for all edges. To address this issue,
this work proposes a fine-grained privacy notion as well as novel algorithms
for private graph analysis. We first design a fine-grained relationship
differential privacy (FGR-DP) notion for social graph analysis, which enforces
different protections for the edges with distinct privacy requirements. Then,
we design algorithms for triangle counting and k-stars counting, respectively,
which can accurately estimate subgraph counts given fine-grained protection for
social edges. We also analyze upper bounds on the estimation error, including
k-stars and triangle counts, and show their superior performance compared with
the state-of-the-arts. Finally, we perform extensive experiments on two real
social graph datasets and demonstrate that the proposed mechanisms satisfying
FGR-DP have better utility than the state-of-the-art mechanisms due to the
finer-grained protection.
