analiza aiqbench
This paper introduces the first efficient algorithms for differentially private range subgraph counting, addressing the high sensitivity inherent in nonlinear graph analytics. By projecting the problem to weighted orthogonal range counting, the authors achieve accurate query answering with small additive error while establishing theoretical lower bounds that prove error must grow exponentially with dimensionality. The work provides a critical foundation for privacy-preserving graph analytics in high-dimensional attribute spaces.
Differentially Private Range Subgraph Counting
arXiv:2606.08179v1 Announce Type: cross 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.
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.
Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR); Machine Learning (cs.LG)
arXiv:2606.08179 [cs.DS]
(or arXiv:2606.08179v1 [cs.DS] for this version)
https://doi.org/10.48550/arXiv.2606.08179 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 292 cuvinte
Subiecte conexe
SenWorld: A Digital-Twin Simulation for Generating Context-Rich Evaluation Data
arXiv · 24 iul. 2026
Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution
arXiv · 9 iun. 2026
SLogic: Subgraph-Informed Logical Rule Learning for Knowledge Graph Completion
arXiv · 25 aug. 2026
Hyperbolic Graph Representation Learning for Differential Diagnosis on Biomedical Knowledge Graphs
arXiv · 17 sept. 2026