EPDQ: Efficient and Privacy-Preserving Exact Distance Query on Encrypted Graphs

• URL: http://arxiv.org/abs/2603.26219v1
• Date: Fri, 27 Mar 2026 09:42:10 GMT
• Title: EPDQ: Efficient and Privacy-Preserving Exact Distance Query on Encrypted Graphs
• Abstract summary: This paper proposes a tensor-based shortest distance query scheme for encrypted graph databases.<n>It integrates an encrypted 2-hop cover indexing framework with the Pruned Landmark Labeling (PLL) technique.<n>It achieves superior scalability and lower computational costs compared with existing encrypted graph query methods.
• Score: 0.6768558752130311
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With the explosive growth of graph-structured data, graph databases have become a critical infrastructure for supporting large-scale and complex data analysis. Among various graph operations, shortest distance queries play a fundamental role in numerous applications, such as path planning, recommendation systems, and knowledge graphs. However, existing encrypted graph query methods still suffer from limitations in computational efficiency and system scalability, making it challenging to support efficient query processing over large-scale encrypted graph data. To address these challenges, this paper proposes a tensor-based shortest distance query scheme for encrypted graph databases. The proposed method integrates an encrypted 2-hop cover indexing framework with the Pruned Landmark Labeling (PLL) technique, thereby constructing an efficient and privacy-preserving indexing mechanism. Furthermore, a tensorized representation is introduced to uniformly model graph structures, which effectively reduces computational complexity while ensuring data privacy, and significantly improves the scalability of the system. Extensive experimental evaluations on large-scale graph datasets demonstrate that the proposed approach achieves superior scalability and lower computational costs compared with existing encrypted graph query methods. Moreover, it provides strong privacy protection guarantees, making it well suited for privacy-preserving graph query applications in cloud computing and distributed environments.

Related papers

• DESIGN: Encrypted GNN Inference via Server-Side Input Graph Pruning [21.652233892742366]
  DESIGN (EncrypteD GNN Inference via sErver-Side Input Graph pruNing) is a novel framework for efficient encrypted GNN inference.<n>Our framework achieves significant performance gains through a hierarchical optimization strategy executed entirely on the server.
  arXiv  Detail & Related papers  (2025-07-08T04:01:53Z)
• Geometry-Aware Edge Pooling for Graph Neural Networks [23.216349399814643]
  Graph Neural Networks (GNNs) have shown significant success for graph-based tasks.<n>Motivated by the prevalence of large datasets in real-world applications, pooling layers are crucial components of GNNs.<n>We propose novel graph pooling layers for structure-aware pooling via edge collapses.
  arXiv  Detail & Related papers  (2025-06-13T12:01:46Z)
• 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)
• Verifiable, Efficient and Confidentiality-Preserving Graph Search with Transparency [16.64649629947436]
  PeGraph is the latest scheme achieving encrypted search over social graphs to address the privacy leakage.<n>It does not provide transparent search capabilities, suffers from expensive computation and result pattern leakages.<n>We propose SecGraph to address the first two limitations, which adopts a novel system architecture.
  arXiv  Detail & Related papers  (2025-03-13T08:53:53Z)
• FedGraph: A Research Library and Benchmark for Federated Graph Learning [57.769105634569314]
  Federated graph learning is an emerging field with significant practical challenges.<n>We introduce FedGraph, a research library designed for practical distributed training.<n>FedGraph supports a range of state-of-the-art graph learning methods and includes a monitoring class that evaluates system performance.
  arXiv  Detail & Related papers  (2024-10-08T20:18:18Z)
• Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
  Graph learning models have been widely deployed in collaborative filtering (CF) based recommendation systems. Due to the issue of data sparsity, the graph structure of the original input lacks potential positive preference edges. We propose an Amplify Graph Learning framework based on Sparsity Completion (called AGL-SC)
  arXiv  Detail & Related papers  (2024-06-27T08:26:20Z)
• 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)
• Privacy-Preserving Graph Embedding based on Local Differential Privacy [26.164722283887333]
  We introduce a novel privacy-preserving graph embedding framework, named PrivGE, to protect node data privacy. Specifically, we propose an LDP mechanism to obfuscate node data and utilize personalized PageRank as the proximity measure to learn node representations. Experiments on several real-world graph datasets demonstrate that PrivGE achieves an optimal balance between privacy and utility.
  arXiv  Detail & Related papers  (2023-10-17T08:06:08Z)
• A fast topological approach for predicting anomalies in time-varying graphs [0.0]
  A persistence diagram (PD) from topological data analysis (TDA) has become a popular descriptor of shape of data with a well-defined distance between points. This paper introduces a computationally efficient framework to extract shape information from graph data. In a real data application, our approach provides up to 22% gain in anomalous price prediction for the cryptocurrency transaction networks.
  arXiv  Detail & Related papers  (2023-05-11T01:54:45Z)
• 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)
• Graph Pooling with Maximum-Weight $k$-Independent Sets [12.251091325930837]
  We introduce a graph coarsening mechanism based on the graph-theoretic concept of maximum-weight $k$-independent sets. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs.
  arXiv  Detail & Related papers  (2022-08-06T14:12:47Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• 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)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)

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.