Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

An Efficient Framework for Multiple Subgraph Pattern Matching Models

  • Regular Paper
  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

Abstract

With the popularity of storing large data graph in cloud, the emergence of subgraph pattern matching on a remote cloud has been inspired. Typically, subgraph pattern matching is defined in terms of subgraph isomorphism, which is an NP-complete problem and sometimes too strict to find useful matches in certain applications. And how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results is an important concern. Thus, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching in cloud. In order to protect the structural privacy in data graphs, we firstly develop a k-automorphism model based method. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. During the generation of the k-automorphic graph, a large number of noise edges or vertices might be introduced to the original data graph. Thus, we use the outsourced graph, which is only a subset of a k-automorphic graph, to answer the subgraph pattern matching. The efficiency of the pattern matching process can be greatly improved in this way. Extensive experiments on real-world datasets demonstrate the high efficiency of our framework.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Lu H, Chang Y. Mining disease transmission networks from health insurance claims. In Proc. the 2017 International Conference on Smart Health, June 2017, pp.268-273.

  2. Ray B, Ghedin E, Chunara R. Network inference from multimodal data: A review of approaches from infectious disease transmission. Journal of Biomedical Informatics, 2016, 64: 44-54.

    Article  Google Scholar 

  3. Balsa E, Pérez-Solà C, Díaz C. Towards inferring communication patterns in online social networks. ACM Trans. Internet Techn., 2017, 17(3): Article No. 32.

    Article  Google Scholar 

  4. Yin H, Zhou X, Cui B, Wang H, Zheng K, Hung N Q V. Adapting to user interest drift for POI recommendation. IEEE Trans. Knowl. Data Eng., 2016, 28(10): 2566-2581. [5] Yin H, Hu Z, Zhou X, Wang H, Zheng K, Hung N Q V, Sadiq S W. Discovering interpretable geo-social communities for user behavior prediction. In Proc. the 32nd IEEE International Conference on Data Engineering, May 2016, pp.942-953.

  5. Xie M, Yin H, Wang H, Xu F, Chen W, Wang S. Learning graph-based POI embedding for location-based recommendation. In Proc. the 25th ACM International Conference on Information and Knowledge Management, October 2016, pp.15-24.

  6. Yin H, Wang W, Wang H, Chen L, Zhou X. Spatial-aware hierarchical collaborative deep learning for POI recom- mendation. IEEE Trans. Knowl. Data Eng., 2017, 29(11): 2537-2551.

    Article  Google Scholar 

  7. Aggarwal C C, Wang H. Managing and Mining Graph Data. Spring, 2010.

  8. Gallagher B. Matching structure and semantics: A survey on graph-based pattern matching. In Proc. the 2006 AAAI Fall Symposium on Capturing and Using Patterns for Evidence Detection, October 2006, pp.45-53.

  9. Henzinger M R, Henzinger T A, Kopke P W. Computing simulations on finite and infinite graphs. In Proc. the 36th Annual Symposium on Foundations of Computer Science, October 1995, pp.453-462.

  10. Fan W, Li J, Ma S, Tang N, Wu Y, Wu Y. Graph pattern matching: From intractable to polynomial time. Proceedings of the VLDB Endowment, 2010, 3(1): 264-275.

    Article  Google Scholar 

  11. Brynielsson J, Högberg J, Kaati L, Mårtenson C, Svenson P. Detecting social positions using simulation. In Proc. the 2010 International Conference on Advances in Social Networks Analysis and Mining, August 2010, pp.48-55.

  12. Ma S, Cao Y, Fan W, Huai J, Wo T. Strong simulation: Capturing topology in graph pattern matching. ACM Trans. Database Syst., 2014, 39(1): Article No. 4.

    Article  MathSciNet  Google Scholar 

  13. Fard A, Nisar M U, Ramaswamy L, Miller J A, Saltz M. A distributed vertex-centric approach for pattern matching in massive graphs. In Proc. the 2013 IEEE International Conference on Big Data, October 2013, pp.403-411.

  14. Fard A, Nisar M U, Miller J A, Ramaswamy L. Distributed and scalable graph pattern matching: Models and algorithms. International Journal of Big Data, 2014, 1(1): 1-14.

    Article  Google Scholar 

  15. Fan W, Li J, Ma S, Tang N, Wu Y. Adding regular expressions to graph reachability and pattern queries. In Proc. the 27th International Conference on Data Engineering, April 2011, pp.39-50.

  16. Chang Z, Zou L, Li F. Privacy preserving subgraph matching on large graphs in cloud. In Proc. the 2016 International Conference on Management of Data, June 2016, pp.199-213.

  17. Zou L, Chen L, Özsu M T. K-automorphism: A general framework for privacy preserving network publication. Proceedings of the VLDB Endowment, 2009, 2(1): 946-957.

    Article  Google Scholar 

  18. Tai C, Tseng P, Yu P S, Chen M. Identity protection in sequential releases of dynamic networks. IEEE Trans. Knowl. Data Eng., 2014, 26(3): 635-651.

    Article  Google Scholar 

  19. Liu K, Terzi E. Towards identity anonymization on graphs. In Proc. the ACM SIGMOD International Conference on Management of Data, June 2008, pp.93-106.

  20. Zhou B, Pei J. Preserving privacy in social networks against neighborhood attacks. In Proc. the 24th International Conference on Data Engineering, April 2008, pp.506-515.

  21. Li J, Xiong J, Wang X. The structure and evolution of large cascades in online social networks. In Proc. the 4th International Conference on Computational Social Networks, August 2015, pp. 273-284.

  22. Hay M, Miklau G, Jensen D et al. Resisting structural re-identification in anonymized social networks. VLDB, 2010, 19(6): 797-823.

    Article  Google Scholar 

  23. Cheng J, Fu A W, Liu J. K-isomorphism: Privacy preserving network publication against structural attacks. In Proc. the ACM SIGMOD International Conference on Management of Data, June 2010, pp. 459-470.

  24. Wu W, Xiao Y, Wang W et al. K-symmetry model for identity anonymization in social networks. In Proc. the 13th International Conference on Extending Database Technology, March 2010, pp.111-122.

  25. Liu K, Terzi E. Towards identity anonymization on graphs. In Proc. the ACM SIGMOD International Conference on Management of Data, June 2008, pp.93-106.

  26. Tai C H, Yu P S, Yang D H, Chen M S. Privacy preserving social network publication against friendship attacks. In Proc. the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2011, pp.1262-1270.

  27. Chen S, Zhou S. Recursive mechanism: Towards node differential privacy and unrestricted joins. In Proc. the ACM SIGMOD International Conference on Management of Data, June 2013, pp.653-664.

  28. Zhu T, Li G, Zhou W, Yu P S. Differentially private data publishing and analysis: A survey. IEEE Trans. Knowl. Data Eng., 2017, 29(8): 1619-1638.

    Article  Google Scholar 

  29. Qian Q, Li Z, Zhao P et al. Publishing graph node strength histogram with edge differential privacy. In Proc. the 23rd International Conference Database Systems for Advanced Applications, May 2018, pp.75-91.

  30. Sala A, Zhao X, Wilson C et al. Sharing graphs using differentially private graph models. In Proc. the 11th ACM SIGCOMM Internet Measurement Conference, November 2011, pp.81-98.

  31. Chen R, Fung B C, Yu P S et al. Correlated network data publication via differential privacy. VLDB, 2014, 23(4): 653-676.

    Article  Google Scholar 

  32. Zhang J, Cormode G, Procopiuc C M et al. Private release of graph statistics using ladder functions. In Proc. the 2015 ACM SIGMOD International Conference on Management of Data, May 2015, pp.731-745.

  33. Ullmann J R. An algorithm for subgraph isomorphism. J. ACM, 1976, 23(1): 31-42.

    Article  MathSciNet  Google Scholar 

  34. Yuan Y, Wang G, Chen L et al. Efficient subgraph similarity search on large probabilistic graph databases. VLDB, 2012, 5(9): 800-811.

    Google Scholar 

  35. Yuan Y, Wang G, Xu J Y et al. Efficient distributed subgraph similarity matching. VLDB, 2015, 24(3): 369-394.

    Article  Google Scholar 

  36. Gao J, Xu J, Liu G et al. A privacy-preserving frame-work for subgraph pattern matching in cloud. In Proc. the 23rd International Conference on Database Systems for Advanced Applications, May 2018, pp.307-322.

  37. Karypis G, Kumar V. Analysis of multilevel graph partitioning. In Proc. the 1995 ACM/IEEE Conference on Supercomputing, December 1995.

  38. Karypis G, Kumar V. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed computing, 1998, 48(1): 96-129.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Soochow University, Suzhou, 215006, China

    Jiu-Ru Gao, Wei Chen, Jia-Jie Xu, An Liu, Zhi-Xu Li & Lei Zhao

  2. School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, 4072, Australia

    Hongzhi Yin

Authors
  1. Jiu-Ru Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jia-Jie Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. An Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Zhi-Xu Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Hongzhi Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Lei Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lei Zhao.

Electronic supplementary material

ESM 1

(PDF 360 kb)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gao, JR., Chen, W., Xu, JJ. et al. An Efficient Framework for Multiple Subgraph Pattern Matching Models. J. Comput. Sci. Technol. 34, 1185–1202 (2019). https://doi.org/10.1007/s11390-019-1969-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11390-019-1969-x

Keywords

Search

Navigation