Fully Dynamic Graph Algorithms with Edge Differential Privacy

• URL: http://arxiv.org/abs/2409.17623v1
• Date: Thu, 26 Sep 2024 08:17:49 GMT
• Title: Fully Dynamic Graph Algorithms with Edge Differential Privacy
• Authors: Sofya Raskhodnikova, Teresa Anna Steiner,
• Abstract summary: We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only. We give upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems.
• Score: 1.4732811715354455
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, and the algorithm is required to update the solution at every time step. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only (called partially dynamic algorithms) and obtained some hardness results for the fully dynamic setting. The only algorithms in the latter setting were for the edge count, given by Fichtenberger, Henzinger, and Ost (ESA 21), and for releasing the values of all graph cuts, given by Fichtenberger, Henzinger, and Upadhyay (ICML 23). We provide the first differentially private and fully dynamic graph algorithms for several other fundamental graph statistics (including the triangle count, the number of connected components, the size of the maximum matching, and the degree histogram), analyze their error and show strong lower bounds on the error for all algorithms in this setting. We study two variants of edge differential privacy for fully dynamic graph algorithms: event-level and item-level. We give upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems. No fully dynamic algorithms that are private at the item-level (the more stringent of the two notions) were known before. In the case of item-level privacy, for several problems, our algorithms match our lower bounds.

Related papers

• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph. We conclude with additive error lower bounds for edge-privacy in the fully dynamic setting.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
  arXiv  Detail & Related papers  (2024-03-21T11:57:16Z)
• Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation [1.42693144277707]
  We describe the first algorithms that satisfy the standard notion of node-differential privacy in the continual release setting. Previous work addresses node-private continual release by assuming an unenforced promise on the maximum degree in a graph. Our algorithms are accurate on sparse graphs, for several fundamental graph problems.
  arXiv  Detail & Related papers  (2024-03-07T16:14:08Z)
• Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
  We consider the problem of graph searching with prediction recently introduced by Banerjee et al. In this problem, an agent, starting at some $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$. We design algorithms for this search task on unknown graphs.
  arXiv  Detail & Related papers  (2024-02-27T18:12:58Z)
• Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
  We propose improved exact and labeling algorithms for solving the maximum weight clique problem. Our algorithms interleave successful techniques with novel data reduction rules that use local graph structure. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs.
  arXiv  Detail & Related papers  (2023-02-01T14:02:06Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner? Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
  arXiv  Detail & Related papers  (2021-06-08T16:10:36Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• 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)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.