Verifiable, Efficient and Confidentiality-Preserving Graph Search with Transparency

• URL: http://arxiv.org/abs/2503.10171v1
• Date: Thu, 13 Mar 2025 08:53:53 GMT
• Title: Verifiable, Efficient and Confidentiality-Preserving Graph Search with Transparency
• Authors: Qiuhao Wang, Xu Yang, Yiwei Liu, Saiyu Qi, Hongguang Zhao, Ke Li, Yong Qi,
• Abstract summary: 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.
• Score: 16.64649629947436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph databases have garnered extensive attention and research due to their ability to manage relationships between entities efficiently. Today, many graph search services have been outsourced to a third-party server to facilitate storage and computational support. Nevertheless, the outsourcing paradigm may invade the privacy of graphs. PeGraph is the latest scheme achieving encrypted search over social graphs to address the privacy leakage, which maintains two data structures XSet and TSet motivated by the OXT technology to support encrypted conjunctive search. However, PeGraph still exhibits limitations inherent to the underlying OXT. It does not provide transparent search capabilities, suffers from expensive computation and result pattern leakages, and it fails to support search over dynamic encrypted graph database and results verification. In this paper, we propose SecGraph to address the first two limitations, which adopts a novel system architecture that leverages an SGX-enabled cloud server to provide users with secure and transparent search services since the secret key protection and computational overhead have been offloaded to the cloud server. Besides, we design an LDCF-encoded XSet based on the Logarithmic Dynamic Cuckoo Filter to facilitate efficient plaintext computation in trusted memory, effectively mitigating the risks of result pattern leakage and performance degradation due to exceeding the limited trusted memory capacity. Finally, we design a new dynamic version of TSet named Twin-TSet to enable conjunctive search over dynamic encrypted graph database. In order to support verifiable search, we further propose VSecGraph, which utilizes a procedure-oriented verification method to verify all data structures loaded into the trusted memory, thus bypassing the computational overhead associated with the client's local verification.

Related papers

• 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)
• ProGQL: A Provenance Graph Query System for Cyber Attack Investigation [6.954627558521413]
  Provenance analysis (PA) has emerged as an important solution for cyber attack investigation.<n>Existing PA techniques are inflexible and non-extensible, making it difficult to incorporate analyst expertise.<n>We propose the ProGQL framework, which provides a domain-specific graph search language with a well-engineered query engine.
  arXiv  Detail & Related papers  (2025-10-25T18:53:49Z)
• GraphSearch: An Agentic Deep Searching Workflow for Graph Retrieval-Augmented Generation [35.65907480060404]
  textscGraphSearch is a novel agentic deep searching workflow with dual-channel retrieval for GraphRAG.<n>textscGraphSearch consistently improves answer accuracy and generation quality over the traditional strategy.
  arXiv  Detail & Related papers  (2025-09-26T07:45:56Z)
• Threshold-Protected Searchable Sharing: Privacy Preserving Aggregated-ANN Search for Collaborative RAG [0.0]
  Two key bottlenecks are private data repositories' locality constraints and the need to maintain compatibility with mainstream search techniques.<n>We develop a secure and privacy-preserving aggregated approximate nearest neighbor search (SP-A$2$NN) with HNSW compatibility.<n>We also explore a novel security analytical framework that incorporates privacy analysis via reductions.
  arXiv  Detail & Related papers  (2025-07-23T04:45:01Z)
• VeriFuzzy: A Dynamic Verifiable Fuzzy Search Service for Encrypted Cloud Data [13.863905835870836]
  Service that supports dynamic, verifiable fuzzy search (DVFS) over encrypted cloud data remains a fundamental challenge.<n>This paper presents textbfVeriFuzzy, a novel DVFS service framework that cohesively integrates three innovations.<n>Our code and dataset are now open source, hoping to inspire future DVFS research.
  arXiv  Detail & Related papers  (2025-07-15T02:36:30Z)
• GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval [3.792463570467098]
  GraphRunner is a novel graph-based retrieval framework that operates in three distinct stages: planning, verification, and execution.<n>It significantly reduces reasoning errors and detects hallucinations before execution.<n>Our evaluation using the GRBench dataset shows that GraphRunner consistently outperforms existing approaches.
  arXiv  Detail & Related papers  (2025-07-11T18:10:01Z)
• 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)
• 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. RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components. 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)
• TOBUGraph: Knowledge Graph-Based Retrieval for Enhanced LLM Performance Beyond RAG [3.8704987495086542]
  TOBUGraph is a graph-based retrieval framework that first constructs the knowledge graph from unstructured data. It extracts structured knowledge and diverse relationships among data, going beyond RAG's text-to-text similarity. We demonstrate TOBUGraph's effectiveness in TOBU, a real-world application in production for personal memory organization and retrieval.
  arXiv  Detail & Related papers  (2024-12-06T22:05:39Z)
• HOPE: Homomorphic Order-Preserving Encryption for Outsourced Databases -- A Stateless Approach [1.1701842638497677]
  Homomorphic OPE (HOPE) is a new OPE scheme that eliminates client-side storage and avoids additional client-server interaction during query execution. We provide a formal cryptographic analysis of HOPE, proving its security under the widely accepted IND-OCPA model.
  arXiv  Detail & Related papers  (2024-11-26T00:38:46Z)
• Towards Lightweight Graph Neural Network Search with Curriculum Graph Sparsification [48.334100429553644]
  This paper proposes to design a joint graph data and architecture mechanism, which identifies important sub-architectures via the valuable graph data. To search for optimal lightweight Graph Neural Networks (GNNs), we propose a Lightweight Graph Neural Architecture Search with Graph SparsIfication and Network Pruning (GASSIP) method. Our method achieves on-par or even higher node classification performance with half or fewer model parameters of searched GNNs and a sparser graph.
  arXiv  Detail & Related papers  (2024-06-24T06:53:37Z)
• A Privacy-Preserving Graph Encryption Scheme Based on Oblivious RAM [0.0]
  We propose a novel graph encryption scheme designed to mitigate access pattern and query pattern leakage. Our solution establishes two key security objectives: (1) ensuring that adversaries, when presented with an encrypted graph, remain oblivious to any information regarding the underlying graph, and (2) achieving query indistinguishability by concealing access patterns.
  arXiv  Detail & Related papers  (2024-05-29T16:47:38Z)
• SecGraph: Towards SGX-based Efficient and Confidentiality-Preserving Graph Search [13.00839243715644]
  We propose an SGX-based efficient and confidentiality-preserving graph search scheme SecGraph. We show that SecGraph yields up to 208x improvement in search time compared with PeGraph.
  arXiv  Detail & Related papers  (2024-03-28T16:06:13Z)
• 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)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  We propose Automatic Relation-aware Graph Network Proliferation (ARGNP) for efficiently searching GNNs. These operations can extract hierarchical node/relational information and provide anisotropic guidance for message passing on a graph. Experiments on six datasets for four graph learning tasks demonstrate that GNNs produced by our method are superior to the current state-of-the-art hand-crafted and search-based GNNs.
  arXiv  Detail & Related papers  (2022-05-31T10:38:04Z)
• GraphSearchNet: Enhancing GNNs via Capturing Global Dependency for Semantic Code Search [15.687959123626003]
  We design a novel neural network framework, named GraphSearchNet, to enable an effective and accurate source code search. Specifically, we propose to encode both source code and queries into two graphs with BiGGNN to capture the local structure information of the graphs. The experiments on both Java and Python datasets illustrate that GraphSearchNet outperforms current state-of-the-art works by a significant margin.
  arXiv  Detail & Related papers  (2021-11-04T07:38:35Z)
• Deep Fraud Detection on Non-attributed Graph [61.636677596161235]
  Graph Neural Networks (GNNs) have shown solid performance on fraud detection. labeled data is scarce in large-scale industrial problems, especially for fraud detection. We propose a novel graph pre-training strategy to leverage more unlabeled data.
  arXiv  Detail & Related papers  (2021-10-04T03:42:09Z)
• Edge-featured Graph Neural Architecture Search [131.4361207769865]
  We propose Edge-featured Graph Neural Architecture Search to find the optimal GNN architecture. Specifically, we design rich entity and edge updating operations to learn high-order representations. We show EGNAS can search better GNNs with higher performance than current state-of-the-art human-designed and searched-based GNNs.
  arXiv  Detail & Related papers  (2021-09-03T07:53:18Z)
• NASGEM: Neural Architecture Search via Graph Embedding Method [41.0658375655084]
  We propose NASGEM which stands for Neural Architecture Search via Graph Embedding Method. It is driven by a novel graph embedding method equipped with similarity measures to capture the graph topology information. It consistently outperforms networks crafted by existing search methods in classification tasks.
  arXiv  Detail & Related papers  (2020-07-08T21:58:37Z)
• Weakly Supervised Visual Semantic Parsing [49.69377653925448]
  Scene Graph Generation (SGG) aims to extract entities, predicates and their semantic structure from images. Existing SGG methods require millions of manually annotated bounding boxes for training. We propose Visual Semantic Parsing, VSPNet, and graph-based weakly supervised learning framework.
  arXiv  Detail & Related papers  (2020-01-08T03:46:13Z)

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.