Privacy-Preserving Subgraph Checking

Stefan Wüller; Benjamin Assadsolimani; Ulrike Meyer; Susanne Wetzel

doi:10.1109/PST.2018.8514182

Privacy-Preserving Subgraph Checking

Stefan Wüller, Benjamin Assadsolimani, Ulrike Meyer, Susanne Wetzel

Department of Computer Science

RWTH Aachen University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

A subgraph check is a variant of the common subgraph matching-operating on a reference and a test graph- determining whether a test graph is a subgraph of the reference graph. In this paper, we present two novel privacy-preserving subgraph checking protocols. In our first protocol, all subgraph checks are carried out independently of each other. The second protocol allows for a substantial performance improvement over the straight-forward approach of the first protocol by exploiting structural similarities among the test graphs to be checked against the reference graph.

Original language	English
Title of host publication	2018 16th Annual Conference on Privacy, Security and Trust, PST 2018
Editors	Robert H. Deng, Stephen Marsh, Jason Nurse, Rongxing Lu, Sakir Sezer, Paul Miller, Liqun Chen, Kieran McLaughlin, Ali Ghorbani
ISBN (Electronic)	9781538674932
DOIs	https://doi.org/10.1109/PST.2018.8514182
State	Published - 29 Oct 2018
Event	16th Annual Conference on Privacy, Security and Trust, PST 2018 - Belfast, Northern Ireland, United Kingdom Duration: 28 Aug 2018 → 30 Aug 2018

Publication series

Name	2018 16th Annual Conference on Privacy, Security and Trust, PST 2018

Conference

Conference	16th Annual Conference on Privacy, Security and Trust, PST 2018
Country/Territory	United Kingdom
City	Belfast, Northern Ireland
Period	28/08/18 → 30/08/18

Access to Document

10.1109/PST.2018.8514182

Cite this

Wüller, S., Assadsolimani, B., Meyer, U., & Wetzel, S. (2018). Privacy-Preserving Subgraph Checking. In R. H. Deng, S. Marsh, J. Nurse, R. Lu, S. Sezer, P. Miller, L. Chen, K. McLaughlin, & A. Ghorbani (Eds.), 2018 16th Annual Conference on Privacy, Security and Trust, PST 2018 Article 8514182 (2018 16th Annual Conference on Privacy, Security and Trust, PST 2018). https://doi.org/10.1109/PST.2018.8514182

Wüller, Stefan ; Assadsolimani, Benjamin ; Meyer, Ulrike et al. / Privacy-Preserving Subgraph Checking. 2018 16th Annual Conference on Privacy, Security and Trust, PST 2018. editor / Robert H. Deng ; Stephen Marsh ; Jason Nurse ; Rongxing Lu ; Sakir Sezer ; Paul Miller ; Liqun Chen ; Kieran McLaughlin ; Ali Ghorbani. 2018. (2018 16th Annual Conference on Privacy, Security and Trust, PST 2018).

@inproceedings{60c9dd86eb174d73965271699f681482,

title = "Privacy-Preserving Subgraph Checking",

abstract = "A subgraph check is a variant of the common subgraph matching-operating on a reference and a test graph- determining whether a test graph is a subgraph of the reference graph. In this paper, we present two novel privacy-preserving subgraph checking protocols. In our first protocol, all subgraph checks are carried out independently of each other. The second protocol allows for a substantial performance improvement over the straight-forward approach of the first protocol by exploiting structural similarities among the test graphs to be checked against the reference graph.",

author = "Stefan W{\"u}ller and Benjamin Assadsolimani and Ulrike Meyer and Susanne Wetzel",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 16th Annual Conference on Privacy, Security and Trust, PST 2018 ; Conference date: 28-08-2018 Through 30-08-2018",

year = "2018",

month = oct,

day = "29",

doi = "10.1109/PST.2018.8514182",

language = "English",

series = "2018 16th Annual Conference on Privacy, Security and Trust, PST 2018",

editor = "Deng, {Robert H.} and Stephen Marsh and Jason Nurse and Rongxing Lu and Sakir Sezer and Paul Miller and Liqun Chen and Kieran McLaughlin and Ali Ghorbani",

booktitle = "2018 16th Annual Conference on Privacy, Security and Trust, PST 2018",

}

Wüller, S, Assadsolimani, B, Meyer, U & Wetzel, S 2018, Privacy-Preserving Subgraph Checking. in RH Deng, S Marsh, J Nurse, R Lu, S Sezer, P Miller, L Chen, K McLaughlin & A Ghorbani (eds), 2018 16th Annual Conference on Privacy, Security and Trust, PST 2018., 8514182, 2018 16th Annual Conference on Privacy, Security and Trust, PST 2018, 16th Annual Conference on Privacy, Security and Trust, PST 2018, Belfast, Northern Ireland, United Kingdom, 28/08/18. https://doi.org/10.1109/PST.2018.8514182

Privacy-Preserving Subgraph Checking. / Wüller, Stefan; Assadsolimani, Benjamin; Meyer, Ulrike et al.
2018 16th Annual Conference on Privacy, Security and Trust, PST 2018. ed. / Robert H. Deng; Stephen Marsh; Jason Nurse; Rongxing Lu; Sakir Sezer; Paul Miller; Liqun Chen; Kieran McLaughlin; Ali Ghorbani. 2018. 8514182 (2018 16th Annual Conference on Privacy, Security and Trust, PST 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Privacy-Preserving Subgraph Checking

AU - Wüller, Stefan

AU - Assadsolimani, Benjamin

AU - Meyer, Ulrike

AU - Wetzel, Susanne

PY - 2018/10/29

Y1 - 2018/10/29

N2 - A subgraph check is a variant of the common subgraph matching-operating on a reference and a test graph- determining whether a test graph is a subgraph of the reference graph. In this paper, we present two novel privacy-preserving subgraph checking protocols. In our first protocol, all subgraph checks are carried out independently of each other. The second protocol allows for a substantial performance improvement over the straight-forward approach of the first protocol by exploiting structural similarities among the test graphs to be checked against the reference graph.

AB - A subgraph check is a variant of the common subgraph matching-operating on a reference and a test graph- determining whether a test graph is a subgraph of the reference graph. In this paper, we present two novel privacy-preserving subgraph checking protocols. In our first protocol, all subgraph checks are carried out independently of each other. The second protocol allows for a substantial performance improvement over the straight-forward approach of the first protocol by exploiting structural similarities among the test graphs to be checked against the reference graph.

UR - http://www.scopus.com/inward/record.url?scp=85063529971&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063529971&partnerID=8YFLogxK

U2 - 10.1109/PST.2018.8514182

DO - 10.1109/PST.2018.8514182

M3 - Conference contribution

AN - SCOPUS:85063529971

T3 - 2018 16th Annual Conference on Privacy, Security and Trust, PST 2018

BT - 2018 16th Annual Conference on Privacy, Security and Trust, PST 2018

A2 - Deng, Robert H.

A2 - Marsh, Stephen

A2 - Nurse, Jason

A2 - Lu, Rongxing

A2 - Sezer, Sakir

A2 - Miller, Paul

A2 - Chen, Liqun

A2 - McLaughlin, Kieran

A2 - Ghorbani, Ali

T2 - 16th Annual Conference on Privacy, Security and Trust, PST 2018

Y2 - 28 August 2018 through 30 August 2018

ER -

Privacy-Preserving Subgraph Checking

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this