Fully Dynamic Graph Algorithms with Edge Differential Privacy

• URL: http://arxiv.org/abs/2409.17623v2
• Date: Mon, 16 Dec 2024 14:26:50 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:
• 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

• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs [0.13654846342364307]
  We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit. We show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring.
  arXiv  Detail & Related papers  (2024-12-19T18:27:39Z)
• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  We make novel use of sparsification techniques from the non-private streaming and static graph algorithms to achieve new results in the sublinear space, continual release setting. 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)
• 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)
• 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.