nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Classifying Large Graphs with Differential Privacy

verfasst von : Fredrik D. Johansson, Otto Frost, Carl Retzner, Devdatt Dubhashi

Erschienen in: Modeling Decisions for Artificial Intelligence

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider classification of graphs using graph kernels under differential privacy. We develop differentially private mechanisms for two well-known graph kernels, the random walk kernel and the graphlet kernel. We use the Laplace mechanism with restricted sensitivity to release private versions of the feature vector representations of these kernels. Further, we develop a new sampling algorithm for approximate computation of the graphlet kernel on large graphs with guarantees on sample complexity, and show that the method improves both privacy and computation speed. We also observe that the number of samples needed to obtain good accuracy in practice is much lower than the bound. Finally, we perform an extensive empirical evaluation examining the trade-off between privacy and accuracy and show that our private method is able to retain good accuracy in several classification tasks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Extremal Completions of Triangular Norms Known on a Subregion of the Unit Interval

http://www.cse.chalmers.se/~frejohk/data/graphdata_aistats2015.zip.

http://www.vbi.vt.edu/ndssl.

http://snap.stanford.edu/.

Blocki, J., Blum, A., Datta, A., Sheffet, O.: The johnson-lindenstrauss transform itself preserves differential privacy. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 410–419 (2012)

Blocki, J., Blum, A., Datta, A., Sheffet, O.: Differentially private data analysis of social networks via restricted sensitivity. In: ITCS, pp. 87–96 (2013)

Borgwardt, K.M., Kriegel, H.-P.: Shortest-path kernels on graphs. In: Proceedings of ICDM, pp. 74–81 (2005)

Dobson, P.D., Doig, A.J.: Distinguishing enzyme structures from non-enzymes without alignments. J. Mol. Biol. 330(4), 771–783 (2003)CrossRefMATH

Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006) CrossRef

Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Theoret. Comput. Sci. 9(3–4), 211–407 (2013)MathSciNet

Gärtner, T., Flach, P.A., Wrobel, S.: On graph kernels: hardness results and efficient alternatives. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 129–143. Springer, Heidelberg (2003) CrossRef

Hermansson, L., Kerola, T., Johansson, F., Jethava, V., Dubhashi, D.: Entity disambiguation in anonymized graphs using graph kernels. In: CIKM 2013, pp. 1037–1046. ACM (2013)

Hubler, C., Kriegel, H.-P., Borgwardt, K., Ghahramani, Z.: Metropolis algorithms for representative subgraph sampling. In: Eighth IEEE International Conference on Data Mining, ICDM 2008, pp. 283–292. IEEE (2008)

10.

Jain, P., Thakurta, A.: Differentially private learning with kernels. In: JMLR Proceedings of ICML 2013, vol. 28, pp. 118–126 (2013). JMLR.org

11.

Jernigan, C., Mistree, B.F.: Gaydar: facebook friendships expose sexual orientation. First Monday 14(10) (2009)

12.

Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: Proceedings of the 20th International Conference on Machine Learning (2003)

13.

Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? In: CoRR (2008)

14.

Kasiviswanathan, S.P., Nissim, K., Raskhodnikova, S., Smith, A.: Analyzing graphs with node differential privacy. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 457–476. Springer, Heidelberg (2013) CrossRef

15.

Kriege, N., Mutzel, P.: Subgraph matching kernels for attributed graphs. In: ICML. icml.cc / Omnipress (2012)

16.

Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)MathSciNetCrossRef

17.

Li, N., Qardaji, W., Su, D.: On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In: ASIACCS 2012, pp. 32–33. ACM, New York (2012)

18.

McSherry, F., Mironov, I.: Differentially private recommender systems: building privacy into the net. In: IV Elder, J.F., Fogelman-Souli, F., Flach, P.A., Zaki, M. (eds.) KDD, pp. 627–636. ACM (2009)

19.

Narayanan, A., Shmatikov, V.: Robust de-anonymization of large sparse datasets. In: 2013 IEEE Symposium on Security and Privacy, pp. 111–125 (2008)

20.

Nissim, K., Raskhodnikova, S., Smith, A.: Smooth sensitivity and sampling in private data analysis. In: STOC 2007, pp. 75–84. ACM (2007)

21.

Rahman, M., Bhuiyan, M., Hasan, M.A.: Graft: an approximate graphlet counting algorithm for large graph analysis. In: CIKM 2012, pp. 1467–1471. ACM (2012)

22.

Schölkopf, B., Smola, A.J.: Learning With Kernels: Support Vector Machines, Regularization, Optimization, And Beyond. MIT Press, Cambridge (2001)

23.

Shervashidze, N.: Scalable graph kernels. Ph.D. thesis, Eberhard Karls Universitt Tbingen (2012)

24.

Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. J. Mach. Learn. Res. 12, 2539–2561 (2011)MathSciNet

25.

Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.M.: Efficient graphlet kernels for large graph comparison. In: Proceedings of AISTATS (2009)

26.

Swarup, S., Eubank, S.G., Marathe, M.V.: Computational epidemiology as a challenge domain for multiagent systems. In: AAMAS 2014, pp. 1173–1176, Richland, SC (2014)

27.

Vishwanathan, S., Schraudolph, N.N., Kondor, R., Borgwardt, K.M.: Graph kernels. J. Mach. Learn. Res. 11, 1201–1242 (2010)MathSciNetMATH

28.

Vishwanathan, S.V.N., Borgwardt, K.M., Schraudolph, N.N.: Fast computation of graph kernels. In: Schkopf, B., Platt, J., Hoffman, T. (eds.) NIPS, pp. 1449–1456. MIT Press (2006)

29.

Woznica, A., Kalousis, A., Hilario, M.: Matching based kernels for labeled graphs. In: ECML/PKDD Workshop on Mining and Learning with Graphs (2006)

Titel: Classifying Large Graphs with Differential Privacy
verfasst von: Fredrik D. Johansson
Otto Frost
Carl Retzner
Devdatt Dubhashi
Verlag: Springer International Publishing
Buch: Modeling Decisions for Artificial Intelligence
Print ISBN: 978-3-319-23239-3

Electronic ISBN: 978-3-319-23240-9

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-23240-9_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner