Sublinear Space Graph Algorithms in the Continual Release Model

• URL: http://arxiv.org/abs/2407.17619v3
• Date: Wed, 16 Apr 2025 03:14:07 GMT
• Title: Sublinear Space Graph Algorithms in the Continual Release Model
• Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, Felix Zhou,
• Abstract summary: 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.
• 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 edge updates where new private solutions are released after each update. Thus far, previously known edge-differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-value estimates (not vertex subset solutions) and do not use sublinear space. Instead, they rely on computing exact graph statistics on the input [FHO21,SLMVC18]. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. 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 the densest subgraph problem, we also output edge-differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space, continual release setting. This includes algorithms for densest subgraph, maximum matching, as well as the first continual release $k$-core decomposition algorithm. We also develop a novel sparse level data structure for $k$-core decomposition that may be of independent interest. To complement our insertion-only algorithms, we conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting, where only logarithmic lower bounds were previously known.

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)
• 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)
• $\ell_2$-norm Flow Diffusion in Near-Linear Time [18.263667346853698]
  We provide an $widetildeO(m)$-time randomized algorithm for the $ell$-norm flow diffusion problem. It is done simply by sweeping over the dual solution vector. It adapts the high-level algorithmic framework of Laplacian system solvers, but requires several new tools.
  arXiv  Detail & Related papers  (2021-05-30T21:27:58Z)
• 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)
• 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)
• 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.