Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model

Introduction

• The problem of counting the number of triangles and 4-cycles in a graph while preserving the privacy of the individuals.
• Previous solutions have focused on the central model, where a trusted third party is responsible for collecting and aggregating the data.
• The shuffle model is an alternative approach that distributes the data among multiple servers and allows them to perform computations on the shuffled data without revealing individual data.

Shuffle Model

• The shuffle model involves three phases: shuffle phase, computation phase, and unshuffle phase.
• In the shuffle phase, the data is randomly shuffled among the servers.
• In the computation phase, each server performs computations on the shuffled data.
• In the unshuffle phase, the results from each server are combined to obtain the final result.

Differential Privacy

• Differential privacy is a privacy notion that guarantees that the output of a computation does not reveal any information about an individual's data.
• A randomized algorithm is said to be differentially private if the output of the algorithm does not change significantly when an individual's data is removed from the input.

Differentially Private Triangle Counting

• The goal of differentially private triangle counting is to estimate the number of triangles in a graph while preserving the privacy of the individuals.
• The algorithm involves adding noise to the count of triangles in each server in the computation phase.
• The noise is added in a way that satisfies differential privacy.
• The noise is removed in the unshuffle phase to obtain the final result.

Differentially Private 4-Cycle Counting

• The goal of differentially private 4-cycle counting is to estimate the number of 4-cycles in a graph while preserving the privacy of the individuals.
• The algorithm involves adding noise to the count of 4-cycles in each server in the computation phase.
• The noise is added in a way that satisfies differential privacy.
• The noise is removed in the unshuffle phase to obtain the final result.

Experimental Results

• The authors conducted experiments on real-world and synthetic datasets to evaluate the performance of the proposed algorithms.
• The results show that the proposed algorithms are effective in preserving privacy while accurately counting triangles and 4-cycles.
• The algorithms also outperform previous solutions in terms of runtime and communication complexity.

Conclusion

• The shuffle model provides an alternative approach for preserving privacy in graph computations.
• The proposed algorithms for differentially private triangle and 4-cycle counting are effective and efficient.
• Future work can explore the applicability of the shuffle model to other types of graph computations