CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Classifying large graphs with differential privacy

Fredrik Johansson (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Otto Frost ; Carl Thufvesson Retzner ; Devdatt Dubhashi (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers))
Lecture Notes in Computer Science - 12th International Conference on Modeling Decisions for Artificial Intelligence, MDAI 2015, Skövde, Sweden, 21-23 September 2015 (0302-9743). Vol. 9321 (2015), p. 3-7.
[Konferensbidrag, refereegranskat]

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.



Denna post skapades 2015-12-11. Senast ändrad 2016-01-05.
CPL Pubid: 227993

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)

Ämnesområden

Datavetenskap (datalogi)

Chalmers infrastruktur