The Power of Graph Sparsification in the Continual Release Model

• URL: http://arxiv.org/abs/2407.17619v1
• Date: Wed, 24 Jul 2024 20:15:07 GMT
• Title: The Power of Graph Sparsification in the Continual Release Model
• Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, Felix Zhou,
• Abstract summary: 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.
• Score: 48.65946341463292
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of updates where new private solutions are released after each update. Streaming graph algorithms in the non-private literature also produce (approximately) accurate solutions when provided updates in a stream, but they additionally try to achieve two other goals: 1) output vertex or edge subsets as approximate solutions to the problem (not just real-valued estimates) and 2) use space that is sublinear in the number of edges or the number of vertices. Thus far, all previously known edge-differentially private algorithms for graph problems in the continual release setting do not meet the above benchmarks. Instead, they require computing exact graph statistics on the input [SLMVC18, FHO21, JSW24]. In this paper, we leverage sparsification to address the above shortcomings. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for most of our problems, we also output differentially private vertex subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature and achieve new results in the sublinear space, continual release setting for a variety of problems including densest subgraph, $k$-core decomposition, maximum matching, and vertex cover. In addition to our edge-differential privacy results, we use graph sparsification based on arboricity to obtain a set of results in the node-differential privacy setting, illustrating a new connection between sparsification and privacy beyond minimizing space. We conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting.

Related papers

• Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
  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.
  arXiv  Detail & Related papers  (2024-09-26T08:17:49Z)
• 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)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Maximal Independent Vertex Set applied to Graph Pooling [0.0]
  Convolutional neural networks (CNN) have enabled major advances in image classification through convolution and pooling. In particular, image pooling transforms a connected discrete grid into a reduced grid with the same connectivity and allows reduction functions to take into account all the pixels of an image. We propose to overcome both problems using a new pooling method, named MIVSPool.
  arXiv  Detail & Related papers  (2022-08-02T14:42:58Z)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
  We consider the problem of learning a graph under the Laplacian constrained Gaussian graphical models. We show that a large regularization parameter will surprisingly lead to a complete graph, i.e., every edge connected by an edge.
  arXiv  Detail & Related papers  (2020-06-26T12:06:10Z)
• 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)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.