Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model
Jacob Imola, Takao Murakami, Kamalika Chaudhuri
2022Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security32 citationsDOIOpen Access PDF
Abstract
Subgraph counting is fundamental for analyzing connection patterns or clustering tendencies in graph data. Recent studies have applied LDP (Local Differential Privacy) to subgraph counting to protect user privacy even against a data collector in social networks. However, existing local algorithms suffer from extremely large estimation errors or assume multi-round interaction between users and the data collector, which requires a lot of user effort and synchronization.
Topics & Concepts
Differential privacyComputer scienceCluster analysisSynchronization (alternating current)GraphTheoretical computer scienceConnection (principal bundle)Graph theoryData miningComputer networkArtificial intelligenceMathematicsCombinatoricsChannel (broadcasting)GeometryStochastic processes and statistical mechanicsMarkov Chains and Monte Carlo MethodsGame Theory and Voting Systems