Differentially Private Range Subgraph Counting

Xian Chen; Ruobing Bai; Pan Peng

cs.DSJun 6, 2026

Differentially Private Range Subgraph Counting

Authors: Xian Chen, Ruobing Bai, Pan Peng

Abstract

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.

Explore similar work

Jul 1, 2026cs.DS

The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

Private continual counting is a fundamental problem in differential privacy: given a binary stream of length

n

, where each

1

corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected

\ell_\infty

error proportional to

\log^{3/2} n

for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on

n

by proving that every differentially private mechanism for continual counting must incur expected

\ell_\infty

error

Ω(\log^{3/2} n)

. This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private

\ell_\infty

error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.

Konstantina Bairaktari, Kasper Green Larsen

Differential Privacy Counting Equal Error Rate

Ask PDF

May 3, 2026cs.LG

Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability

We study differential privacy (DP) in Graph Convolutional Networks (GCNs) through the framework of \textit{subsampling stability}. We derive upper bounds on the misclassification rate that depend explicitly on the subsampling probability

p_s

. Furthermore, we characterize the \textit{privacy--utility trade-off} by identifying feasible ranges of

p_s

; if

p_s

is too large, the stability-based privacy condition becomes difficult to satisfy, yielding vacuous guarantees, whereas if it is too small, accuracy deteriorates. Our results provide the first rigorous theoretical framework for understanding subsampling stability in GCNs under DP.

Yexin Zhang, Zhongtian Ma, Qiaosheng Zhang +1

Differential Privacy Privacy-Utility Trade-Offs

Ask PDF

May 27, 2026cs.CR

Privately Estimating Monotone Statistics in Polynomial Time

We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting point for our investigation is subsample-and-aggregate: a classical paradigm that partitions the dataset into blocks, estimates the statistic on each block, and then privately aggregates the estimates. While practical and generically applicable, this approach is quite data-hungry. We improve upon this framework for the class of monotone statistics -- compared to subsample-and-aggregate, our algorithms save a factor of

t

in sample complexity and pay a factor of

e^t

in running time, where

t>0

is a tunable parameter. We complement our results with a query-complexity lower bound, showing that our algorithms are essentially optimal for this task. As an application, we obtain improved results for private eigenvalue estimation, private loss estimation, and privately estimating a single parameter of a high-dimensional model, e.g., in linear regression.

Gavin Brown, Ephraim Linder, Mahbod Majid +1

Optimal Sample Complexity Statistical Inference Monotonicity Largest Eigenvalue

Ask PDF