# Differentially Private Range Subgraph Counting

arXiv: https://arxiv.org/abs/2606.08179 · HTML: https://mlsanity.com/paper/2606.08179/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 51 references that are in the map.
- First posted on arXiv 6 Jun 2026.

## Builds on (most cited first, 14 of 14)

- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Homomorphisms Are a Good Basis for Counting Small Subgraphs](https://mlsanity.com/paper/1705.01595/) (2017)
- [Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]](https://mlsanity.com/paper/1304.4795/) (2013)
- [Differentially Private Algorithms for Graphs Under Continual Observation](https://mlsanity.com/paper/2106.14756/) (2021)
- [Communication-Efficient Triangle Counting under Local Differential Privacy](https://mlsanity.com/paper/2110.06485/) (2021)
- [Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model](https://mlsanity.com/paper/2205.01429/) (2022)
- [Triangle Counting with Local Edge Differential Privacy](https://mlsanity.com/paper/2305.02263/) (2023)
- [Differentially Private Range Query on Shortest Paths](https://mlsanity.com/paper/2212.07997/) (2022)
- [A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling](https://mlsanity.com/paper/1811.07780/) (2018)
- [Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time](https://mlsanity.com/paper/2005.01861/) (2020)
- [Space-Query Tradeoffs in Range Subgraph Counting and Listing](https://mlsanity.com/paper/2301.03390/) (2023)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)

## Abstract (arXiv)

Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rather than on the entire graph -- and by growing privacy concerns, we initiate the study of differentially private range subgraph counting (DPRSC). The goal is to privately count occurrences of a fixed pattern graph within induced subgraphs defined by multi-dimensional attribute ranges. Unlike classical point counting, subgraph counting is inherently nonlinear and exhibits high sensitivity: a single edge modification can affect many subgraph occurrences. We present the first efficient algorithms for DPRSC with small additive error. Our approach introduces a subgraph projection that reduces DPRSC to weighted orthogonal range counting, enabling the use of range trees and local sensitivity estimation to achieve accurate private query answering. We complement our algorithms with matching lower bounds, obtained by reducing reconstruction attacks to DPRSC and leveraging discrepancy theory. In particular, we show that any differentially private algorithm for DPRSC must incur additive error exponential in the dimension. Empirical evaluations demonstrate that our algorithms significantly outperform baseline methods in accuracy and runtime while maintaining strong privacy guarantees.