Differentially Private Range Subgraph Counting

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.

Many organizations want to count small connection patterns in networks -- for example, friend triangles in social networks or suspicious transaction loops in financial networks -- but only within groups defined by age, location, time, or other attributes. Doing this safely is hard: changing a single connection can affect many pattern counts, and answering many such counting questions can leak private information. We present the first efficient method for answering these questions with rigorous privacy protection by adding carefully chosen noise. Our key idea is to turn each pattern into a simpler representation that can be organized in a fast search structure, so many related queries can share information and require less added noise. We also establish a nearly matching lower bound: when the number of attributes grows, every privacy-preserving method must lose accuracy quickly. This shows that our algorithm is essentially optimal, up to lower-order factors. Experiments on real networks show that our approach is much more accurate and faster than standard baselines while still protecting privacy. This helps make graph analysis more useful in sensitive settings such as healthcare, finance, and social platforms, where both accuracy and privacy matter.