Counting Graphlets of Size k under Local Differential Privacy

2025/05/19 by Vorapong Suppakitpaisarn, Suppakitpaisarn, Vorapong, Donlapark Ponnoprat +5
Computer Science · Decision Sciences · Physics and Astronomy · #Complex Network Analysis Techniques #Computational Complexity (cs.CC) #Data Quality and Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.2505.12954

openalex publication_date 2025/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The problem of counting subgraphs or graphlets under local differential privacy is an important challenge that has attracted significant attention from researchers. However, much of the existing work focuses on small graphlets like triangles or k-stars. In this paper, we propose a non-interactive, locally differentially private algorithm capable of counting graphlets of any size k. When n is the number of nodes in the input graph, we show that the expected ℓ₂ error of our algorithm is O(n^{k - 1}). Additionally, we prove that there exists a class of input graphs and graphlets of size k for which any non-interactive counting algorithm incurs an expected ℓ₂ error of Ω(n^{k - 1}), demonstrating the optimality of our result. Furthermore, we establish that for certain input graphs and graphlets, any locally differentially private algorithm must have an expected ℓ₂ error of Ω(n^{k - 1.5}). Our experimental results show that our algorithm is more accurate than the classical randomized response method.

Citations

• Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
• Making Large Language Models Better Planners with Reasoning-Decision Alignment
• Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
• Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions
• Near-Optimal Differentially Private k-Core Decomposition
• Analysis of the expected L₂ error of an over-parametrized deep neural network estimate learned by gradient descent without regularization
• Triangle Counting with Local Edge Differential Privacy
• Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
• Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model
• Communication-Efficient Triangle Counting under Local Differential Privacy
• Locally Differentially Private Analysis of Graph Statistics
• Locally Private Graph Neural Networks
• The Role of Interactivity in Local Differential Privacy
• Differentially Private Combinatorial Optimization
• Stochastic blockmodels: First steps
• Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias

Related

• Locally Differentially Private Analysis of Graph Statistics
• Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
• Practical and Accurate Local Edge Differentially Private Graph Algorithms
• Triangle Counting with Local Edge Differential Privacy
• Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix