Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems

• URL: http://arxiv.org/abs/2507.17736v2
• Date: Wed, 03 Sep 2025 16:08:01 GMT
• Title: Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems
• Authors: Shreya Meel, Sennur Ulukus,
• Abstract summary: 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.
• Score: 43.914623898157856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs.

Related papers

• The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
  We study the problem of SPIR on graph-replicated database systems.<n>Each message is replicated at exactly two servers.<n>We quantify the minimum amount of common randomness required to achieve the capacity.
  arXiv  Detail & Related papers  (2026-02-18T18:46:58Z)
• 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)
• 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)
• New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage [39.51026717015587]
  We study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems.<n>We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds.
  arXiv  Detail & Related papers  (2025-04-29T16:05:42Z)
• Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
  We consider the private information retrieval problem for a multigraph-based replication system.<n>Our goal is to establish upper and lower bounds on the PIR capacity of the $r$-multigraph.
  arXiv  Detail & Related papers  (2025-01-29T18:48:22Z)
• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  Shapley Interactions (SIs) quantify node contributions and interactions among multiple nodes.<n>By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction.<n>We introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly.
  arXiv  Detail & Related papers  (2025-01-28T13:37:44Z)
• Signed Diverse Multiplex Networks: Clustering and Inference [4.070200285321219]
  The paper introduces a Signed Generalized Random Dot Product Graph (SGRDPG) model, where edges can be positive or negative.<n>The setting is extended to a multiplex version, where all layers have the same collection of nodes and follow the SGRDPG.<n>By employing novel methodologies, our paper ensures strongly consistent clustering of layers and highly accurate subspace estimation.
  arXiv  Detail & Related papers  (2024-02-14T19:37:30Z)
• FedRA: A Random Allocation Strategy for Federated Tuning to Unleash the Power of Heterogeneous Clients [50.13097183691517]
  In real-world federated scenarios, there often exist a multitude of heterogeneous clients with varying computation and communication resources. We propose a novel federated tuning algorithm, FedRA. In each communication round, FedRA randomly generates an allocation matrix. It reorganizes a small number of layers from the original model based on the allocation matrix and fine-tunes using adapters.
  arXiv  Detail & Related papers  (2023-11-19T04:43:16Z)
• Graph Federated Learning for CIoT Devices in Smart Home Applications [23.216140264163535]
  We propose a novel Graph Signal Processing (GSP)-inspired aggregation rule based on graph filtering dubbed G-Fedfilt'' The proposed aggregator enables a structured flow of information based on the graph's topology. It is capable of yielding up to $2.41%$ higher accuracy than FedAvg in the case of testing the generalization of the models.
  arXiv  Detail & Related papers  (2022-12-29T17:57:19Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)
• Multi-Granularity Graph Pooling for Video-based Person Re-Identification [14.943835935921296]
  graph neural networks (GNNs) are introduced to aggregate temporal and spatial features of video samples. Existing graph-based models, like STGCN, perform the textitmean/textitmax pooling on node features to obtain the graph representation. We propose the graph pooling network (GPNet) to learn the multi-granularity graph representation for the video retrieval.
  arXiv  Detail & Related papers  (2022-09-23T13:26:05Z)
• Long Range Graph Benchmark [32.317725340138104]
  MP-GNNs that simply rely on 1-hop message passing often fare better in several existing graph benchmarks. We benchmark both baseline GNNs and Graph Transformer networks to verify that the models which capture long-range dependencies perform significantly better on these tasks.
  arXiv  Detail & Related papers  (2022-06-16T13:33:22Z)
• Jointly Cross- and Self-Modal Graph Attention Network for Query-Based Moment Localization [77.21951145754065]
  We propose a novel Cross- and Self-Modal Graph Attention Network (CSMGAN) that recasts this task as a process of iterative messages passing over a joint graph. Our CSMGAN is able to effectively capture high-order interactions between two modalities, thus enabling a further precise localization.
  arXiv  Detail & Related papers  (2020-08-04T08:25:24Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.