Privacy-Preserving Subgraph Checking

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publication2018 16th Annual Conference on Privacy, Security and Trust, PST 2018
EditorsRobert H. Deng, Stephen Marsh, Jason Nurse, Rongxing Lu, Sakir Sezer, Paul Miller, Liqun Chen, Kieran McLaughlin, Ali Ghorbani
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538674932
DOIs
StatePublished - Oct 29 2018
Event16th Annual Conference on Privacy, Security and Trust, PST 2018 - Belfast, Northern Ireland, United Kingdom
Duration: Aug 28 2018Aug 30 2018

Publication series

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

Conference

Conference16th Annual Conference on Privacy, Security and Trust, PST 2018
CountryUnited Kingdom
CityBelfast, Northern Ireland
Period8/28/188/30/18

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications

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 [8514182] (2018 16th Annual Conference on Privacy, Security and Trust, PST 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/PST.2018.8514182
Wüller, Stefan ; Assadsolimani, Benjamin ; Meyer, Ulrike ; Wetzel, Susanne. / 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. Institute of Electrical and Electronics Engineers Inc., 2018. (2018 16th Annual Conference on Privacy, Security and Trust, PST 2018).
@inproceedings{926de4f3da5647f69c5d12f42a77fcd0,
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",
year = "2018",
month = "10",
day = "29",
doi = "https://doi.org/10.1109/PST.2018.8514182",
language = "English (US)",
series = "2018 16th Annual Conference on Privacy, Security and Trust, PST 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
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",
address = "United States",

}

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, Institute of Electrical and Electronics Engineers Inc., 16th Annual Conference on Privacy, Security and Trust, PST 2018, Belfast, Northern Ireland, United Kingdom, 8/28/18. https://doi.org/10.1109/PST.2018.8514182

Privacy-Preserving Subgraph Checking. / Wüller, Stefan; Assadsolimani, Benjamin; Meyer, Ulrike; Wetzel, Susanne.

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. Institute of Electrical and Electronics Engineers Inc., 2018. 8514182 (2018 16th Annual Conference on Privacy, Security and Trust, PST 2018).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 - https://doi.org/10.1109/PST.2018.8514182

DO - https://doi.org/10.1109/PST.2018.8514182

M3 - Conference contribution

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

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

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