PMatch: A Secure Framework for Querying Private Localized Graph Patterns

Lyu Xu

doi:10.1109/tkde.2026.3718737

PMatch: A Secure Framework for Querying Private Localized Graph Patterns

2026-07-30

0

PRE

AI

DOI：10.1109/tkde.2026.3718737

Original

Original request for help

Save

Abstract

En 中文

This work studies privacy-preserving graph pattern query services in the database outsourcing paradigm. In such a paradigm, users send their queries to a third-party service provider ($\mathsf {SP}$), who has the outsourced large graph data, and $\mathsf {SP}$ computes the query answers. However, as $\mathsf {SP}$ may not always be trusted, the sensitive information of the users’ queries, importantly, the query structures, should be protected. This work adopts the localized graph patterns as practical query semantics for this paradigm, including subgraph homomorphism, subgraph isomorphism, and strong simulation, for which each matched graph pattern is located in a subgraph called ball that has a restriction on its size. To provide privacy-preserving query processing, we propose a general query matching framework called ${\mathsf {PMatch}}$ that not only efficiently computes approximate existence of matched patterns in the ciphertext domain with only false positives so that exact answers can be securely obtained on the user side, but also achieves high accuracy of the existence results by using pruning strategies specifically designed based on different graph structures. Extensive experiments on real-world datasets demonstrate ${\mathsf {PMatch}}$’s efficiency and effectiveness.

Keywords:

Data outsourcing

graph query processing

localized graph pattern matching

user privacy preservation

PMatch: A Secure Framework for Querying Private Localized Graph Patterns

Abstract

Journal

Organization

Cited Papers