Private Information Retrieval on Multigraph-Based Replicated Storage

• URL: http://arxiv.org/abs/2501.17845v2
• Date: Fri, 02 May 2025 23:38:56 GMT
• Title: Private Information Retrieval on Multigraph-Based Replicated Storage
• Authors: Shreya Meel, Xiangliang Kong, Thomas Jacob Maranzatto, Itzhak Tamo, Sennur Ulukus,
• Abstract summary: 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.
• Score: 39.51026717015587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the private information retrieval (PIR) problem for a multigraph-based replication system, where each set of $r$ files is stored on two of the servers according to an underlying $r$-multigraph. Our goal is to establish upper and lower bounds on the PIR capacity of the $r$-multigraph. Specifically, we first propose a construction for multigraph-based PIR systems that leverages the symmetry of the underlying graph-based PIR scheme, deriving a capacity lower bound for such multigraphs. Then, we establish a general upper bound using linear programming, expressed as a function of the underlying graph parameters. Our bounds are demonstrated to be tight for PIR systems on multipaths for even number of vertices.

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)
• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [75.9865035064794]
  Large language models (LLMs) have demonstrated remarkable capabilities, but still struggle with issues like hallucinations and outdated information.<n>Retrieval-augmented generation (RAG) addresses these issues by grounding LLM outputs in external knowledge with an Information Retrieval (IR) system.<n>We propose Align-GRAG, a novel reasoning-guided dual alignment framework in post-retrieval phrase.
  arXiv  Detail & Related papers  (2025-05-22T05:15:27Z)
• 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)
• 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. 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)
• Lightweight yet Efficient: An External Attentive Graph Convolutional Network with Positional Prompts for Sequential Recommendation [8.49353541052153]
  We propose an External Attentive Graph convolutional network with Positional prompts for Sequential recommendation, namely EA-GPS. We show that the proposed EA-GPS outperforms the state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-02-21T09:34:31Z)
• What Are Good Positional Encodings for Directed Graphs? [13.076497906728333]
  We introduce the notion of Walk Profile, a generalization of walk-counting sequences for directed graphs. We propose a novel Multi-q Magnetic Laplacian PE, which extends the Magnetic Laplacian eigenvector-based PE by incorporating multiple potential factors. Our numerical experiments validate the expressiveness of the proposed PEs and demonstrate their effectiveness in solving sorting network satisfiability.
  arXiv  Detail & Related papers  (2024-07-30T15:38:14Z)
• MS-IMAP -- A Multi-Scale Graph Embedding Approach for Interpretable Manifold Learning [1.8124328823188354]
  This paper introduces a framework for multi-scale graph network embedding based on spectral graph wavelets. We show that in Paley-Wiener spaces on graphs, the spectral graph wavelets operator provides greater flexibility and control over smoothness. An additional key advantage of the proposed embedding is its ability to establish a correspondence between the embedding and input feature spaces.
  arXiv  Detail & Related papers  (2024-06-04T20:48:33Z)
• Simple Multigraph Convolution Networks [49.19906483875984]
  Existing multigraph convolution methods either ignore the cross-view interaction among multiple graphs, or induce extremely high computational cost due to standard cross-view operators. This paper proposes a Simple Multi Convolution Networks (SMGCN) which first extracts consistent cross-view topology from multigraphs including edge-level and subgraph-level topology, then performs expansion based on raw multigraphs and consistent topologies. In theory, SMGCN utilizes the consistent topologies in expansion rather than standard cross-view expansion, which performs credible cross-view spatial message-passing, and effectively reduces the complexity of standard expansion.
  arXiv  Detail & Related papers  (2024-03-08T03:27:58Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP) We propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursion call. Annotating comparisons of different graphs concerning their MIS size leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa.
  arXiv  Detail & Related papers  (2023-10-28T10:58:25Z)
• 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)
• Convolutional Learning on Multigraphs [153.20329791008095]
  We develop convolutional information processing on multigraphs and introduce convolutional multigraph neural networks (MGNNs) To capture the complex dynamics of information diffusion within and across each of the multigraph's classes of edges, we formalize a convolutional signal processing model. We develop a multigraph learning architecture, including a sampling procedure to reduce computational complexity. The introduced architecture is applied towards optimal wireless resource allocation and a hate speech localization task, offering improved performance over traditional graph neural networks.
  arXiv  Detail & Related papers  (2022-09-23T00:33:04Z)
• 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)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• 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)

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.