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

• 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)
• GraphPub: Generation of Differential Privacy Graph with High Availability [21.829551460549936]
  Differential privacy (DP) is a common method to protect privacy on graph data. Due to the complex topological structure of graph data, applying DP on graphs often affects the message passing and aggregation of GNN models. We propose graph publisher (GraphPub), which can protect graph topology while ensuring the availability of data is basically unchanged.
  arXiv  Detail & Related papers  (2024-02-28T20:02:55Z)
• Ising on the Graph: Task-specific Graph Subsampling via the Ising Model [1.804478631424646]
  We present an approach for subsampling graph structures using an Ising model defined on either the nodes or edges. Our approach is task-specific as it can learn how to reduce a graph for a specific downstream task in an end-to-end fashion.
  arXiv  Detail & Related papers  (2024-02-15T18:58:18Z)
• 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)
• GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
  We present textbfGraph textbfModel textbfInversion attack (GraphMI), which aims to extract private graph data of the training graph by inverting GNN. Specifically, we propose a projected gradient module to tackle the discreteness of graph edges while preserving the sparsity and smoothness of graph features. We design a graph auto-encoder module to efficiently exploit graph topology, node attributes, and target model parameters for edge inference.
  arXiv  Detail & Related papers  (2021-06-05T07:07:52Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• 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.