New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage

• URL: http://arxiv.org/abs/2504.20888v1
• Date: Tue, 29 Apr 2025 16:05:42 GMT
• Title: New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage
• Authors: Xiangliang Kong, Shreya Meel, Thomas Jacob Maranzatto, Itzhak Tamo, Sennur Ulukus,
• Abstract summary: 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.
• Score: 39.51026717015587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at most $r$ files. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases.

Related papers

• 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)
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [35.16231062731263]
  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)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline.<n>RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components.<n>Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• 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)
• Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Signal Processing [2.039632659682125]
  We propose a framework to construct tight framelet systems on graphs with localized supports based on hierarchical partitions. Our construction provides parametrized graph framelet systems with great generality based on partition trees. We show that our learned graph framelet systems perform superiorly in non-linear approximation and denoising tasks.
  arXiv  Detail & Related papers  (2023-09-07T07:49:43Z)
• MultiSAGE: a multiplex embedding algorithm for inter-layer link prediction [0.0]
  MultiSAGE is a generalization of the GraphSAGE algorithm that allows to embed multiplex networks. We show that MultiSAGE is capable to reconstruct both the intra-layer and the inter-layer connectivity, outperforming GraphSAGE.
  arXiv  Detail & Related papers  (2022-06-24T08:50:55Z)
• 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)
• MultiBiSage: A Web-Scale Recommendation System Using Multiple Bipartite Graphs at Pinterest [53.3951260443916]
  Graph Convolutional Networks (GCN) can efficiently integrate graph structure and node features to learn high-quality node embeddings. At Pinterest, we have developed and deployed PinSage, a data-efficient GCN that learns pin embeddings from the Pin-Board graph. We show that training deep learning models on graphs that captures diverse interactions would result in learning higher-quality pin embeddings.
  arXiv  Detail & Related papers  (2022-05-21T20:04:46Z)
• Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities [128.55790219377315]
  Graph neural networks have emerged as a leading architecture for many graph-level tasks. graph pooling is indispensable for obtaining a holistic graph-level representation of the whole graph.
  arXiv  Detail & Related papers  (2022-04-15T04:02:06Z)
• Diversified Multiscale Graph Learning with Graph Self-Correction [55.43696999424127]
  We propose a diversified multiscale graph learning model equipped with two core ingredients. A graph self-correction (GSC) mechanism to generate informative embedded graphs, and a diversity boosting regularizer (DBR) to achieve a comprehensive characterization of the input graph. Experiments on popular graph classification benchmarks show that the proposed GSC mechanism leads to significant improvements over state-of-the-art graph pooling methods.
  arXiv  Detail & Related papers  (2021-03-17T16:22:24Z)

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.