Differentially Private Range Subgraph Counting

• URL: http://arxiv.org/abs/2606.08179v1
• Date: Sat, 06 Jun 2026 13:56:57 GMT
• Title: Differentially Private Range Subgraph Counting
• Abstract summary: Subgraph counting is a fundamental problem in graph analysis.<n>The goal is to privately count occurrences of a fixed pattern graph within induced subgraphs.<n>We present the first efficient algorithms for DPRSC with small additive error.
• Score: 5.978091728687093
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Sparse Graph Learning from Sparse Data via Fiedler Number Maximization [16.83442282933831]
  We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in RN, and the underlying distribution is unknown.<n>We incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective.<n> Simulation experiments show that Fiedler number robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.
  arXiv  Detail & Related papers  (2026-04-28T21:40:39Z)
• Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
  We study the problem of spectral graph clustering under edge differential privacy (DP)<n>Specifically, we develop three mechanisms: (i) graph perturbation via randomized edge flipping combined with adjacency matrix shuffling, which enforces edge privacy; (ii) private graph projection with additive Gaussian noise in a lower-dimensional space to reduce dimensionality and computational complexity; and (iii) a noisy power iteration method that distributes Gaussian noise across iterations to ensure edge DP while maintaining convergence.
  arXiv  Detail & Related papers  (2025-10-08T15:30:27Z)
• Practical and Accurate Local Edge Differentially Private Graph Algorithms [11.49857418691547]
  We introduce novel LDP algorithms for two fundamental graph statistics: k-core decomposition and triangle counting.<n>Our approach leverages input-dependent private graph properties, specifically the degeneracy and maximum degree of the graph, to improve theoretical utility.<n>Our k-core decomposition achieves errors within 3x of exact values, far outperforming the 131x error in the baseline of Dhulipala et al.
  arXiv  Detail & Related papers  (2025-06-25T20:54:07Z)
• Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization [90.74916553208153]
  We propose PrunE, the first pruning-based graph OOD method that eliminates spurious edges to improve OOD generalizability.<n>PrunE employs two regularization terms to prune spurious edges: 1) graph size constraint to exclude uninformative spurious edges, and 2) $epsilon$-probability alignment to further suppress the occurrence of spurious edges.
  arXiv  Detail & Related papers  (2025-06-06T10:34:48Z)
• CURATE: Scaling-up Differentially Private Causal Graph Discovery [8.471466670802817]
  Differential Privacy (DP) has been adopted to ensure user privacy in Causal Graph Discovery (CGD) We present CURATE, a DP-CGD framework with adaptive privacy budgeting. We show that CURATE achieves higher utility compared to existing DP-CGD algorithms with less privacy-leakage.
  arXiv  Detail & Related papers  (2024-09-27T18:00:38Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  We make novel use of sparsification techniques from the non-private streaming and static algorithms literature to achieve new results in the sublinear space, continual release setting.<n>This includes algorithms for densest subgraph, maximum matching, and the first continual release $k$-core decomposition algorithm.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank [74.53857412207034]
  We propose an algorithm which outputs an approximate PPR and has provably bounded sensitivity to input edges. Our sensitivity-bounded PPR directly implies private algorithms for several tools of graph learning, such as, differentially private (DP) PPR ranking, DP node classification, and DP node embedding.
  arXiv  Detail & Related papers  (2022-07-14T14:08:59Z)
• HSolo: Homography from a single affine aware correspondence [0.0]
  We present a novel procedure for homography estimation that is particularly well suited for inlier-poor domains. Especially at low inlier rates, our novel algorithm provides dramatic performance improvements.
  arXiv  Detail & Related papers  (2020-09-10T17:13:23Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.