Weak Private Information Retrieval for Graph-based Storage

• URL: http://arxiv.org/abs/2607.21014v1
• Date: Thu, 23 Jul 2026 07:55:59 GMT
• Title: Weak Private Information Retrieval for Graph-based Storage
• Abstract summary: Private information retrieval (G-PIR) on a graph-based storage system involves a client which seeks to retrieve a desired file via a query-response protocol.<n>We propose a G-WPIR scheme for arbitrary graphs, and identify the trade-offs it achieves between rate and privacy.
• Score: 3.425341633647624
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A distributed storage system with graph-based replication consists of a collection of databases and the files they contain. The databases (or servers) are represented as the vertices of a graph, while each file is stored in a distinct pair of servers and is represented by an edge of this graph. Private information retrieval (G-PIR) on such a graph-based storage system involves a client which seeks to retrieve a desired file via a query-response protocol, without leaking the identity of the desired file index to any database. The goal of G-PIR is to maximize the rate (reciprocal of the total normalized download) under the privacy constraint. Prior work on G-PIR has involved perfect information-theoretic privacy (i.e., null leakage). However, if the privacy constraint is relaxed, then PIR protocols could be designed that have even higher rates. We term such protocols as Graph-based Weak Private Information Retrieval (G-WPIR) protocols and initiate their formal study in this work. We propose a G-WPIR scheme for arbitrary graphs, and identify the trade-offs it achieves between rate and privacy, under two well known leakage metrics: mutual information leakage and maximal leakage. Our protocol employs minimal subpacketization (representing a file-size constraint) and employs a simple probabilistic query realization to obtain the smooth trade-off. We extend this protocol with some modifications to two special classes of graphs, the complete graphs and the complete bipartite graphs, and identify the corresponding rate-privacy trade-offs achieved.

Related papers

• Local Private Information Retrieval for Graph-Based Replicated Systems [39.20087907351314]
  We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems.<n>In our proposed privacy setting, the user is concerned with hiding the message index from a particular server.<n>We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
  arXiv  Detail & Related papers  (2026-08-31T17:50:47Z)
• Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems [39.20087907351314]
  We introduce a novel setting where the user's privacy is governed by the servers' storage structure.<n>In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server.<n>We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
  arXiv  Detail & Related papers  (2026-05-11T17:25:10Z)
• Private Information Retrieval for Graph-based Replication with Minimal Subpacketization [3.795745240553126]
  We design new minimal-subpacketization schemes for information-theoretic private information retrieval on graph-based replicated databases.<n>In graph-based replication, the system consists of $K$ files replicated across $N$ servers according to a graph with $N$ vertices and $K$ edges.<n>The client wants to retrieve one desired file, while keeping the index of the desired file private from each server via a query-response protocol.
  arXiv  Detail & Related papers  (2026-01-15T00:34:27Z)
• Towards Federated Clustering: A Client-wise Private Graph Aggregation Framework [57.04850867402913]
  Federated clustering addresses the challenge of extracting patterns from decentralized, unlabeled data.<n>We propose Structural Privacy-Preserving Federated Graph Clustering (SPP-FGC), a novel algorithm that innovatively leverages local structural graphs as the primary medium for privacy-preserving knowledge sharing.<n>Our framework achieves state-of-the-art performance, improving clustering accuracy by up to 10% (NMI) over federated baselines while maintaining provable privacy guarantees.
  arXiv  Detail & Related papers  (2025-11-14T03:05:22Z)
• Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
  We revisit the problem of symmetric private information retrieval in settings where the database replication is modeled by a simple graph.<n>We let all the servers share some common randomness, independent of the messages.<n>We quantify the improvement in SPIR capacity, i.e., the maximum ratio of the number of desired and downloaded symbols.
  arXiv  Detail & Related papers  (2025-10-29T17:40:40Z)
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
  symmetric private information retrieval on replicated databases modeled by a simple graph.<n>We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph.
  arXiv  Detail & Related papers  (2025-07-23T17:51:08Z)
• Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching [59.8522166385372]
  Training and inference with graph neural networks (GNNs) on massive graphs has been actively studied since the inception of GNNs. This paper is concerned with minibatch training and inference with GNNs that employ node-wise sampling in distributed settings. We present SALIENT++, which extends the prior state-of-the-art SALIENT system to work with partitioned feature data.
  arXiv  Detail & Related papers  (2023-05-04T21:04:01Z)
• Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
  We study the node classification problem in the hierarchical graph where a 'node' is a graph instance. We propose the Hierarchical Graph Mutual Information (HGMI) and present a way to compute HGMI with theoretical guarantee. We demonstrate the effectiveness of this hierarchical graph modeling and the proposed SEAL-CI method on text and social network data.
  arXiv  Detail & Related papers  (2022-06-11T04:05:29Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)

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.