A lot of data comes in the form of networks, encoding social interactions, biological processes, or the architecture of a computer virus as a graph structure. This data is valuable, but typically contains sensitive personal information that must be protected when the data is shared or published. In this talk, I argue that protecting network data is difficult when the adversary has access to -- even limited -- side information. We explore two instances of such privacy attacks on network data. The first instance is network alignment: the adversary has access to a perturbed version of an anonymized network, and wishes to reconstruct the true matching between the vertex sets of the observable graph and the side information. The second instance is network assembly: a network is published as a large collection of small subgraphs, each of which is anonymized individually; the adversary tries to reconstruct the structure of the original network. For both problems, we give scaling results for perfect inference as well as results from experiments with real network data, and we distill some important lessons for data security and privacy.
Matthias Grossglauser is Associate Professor in the School of Computer and Communication Sciences at EPFL. His current research interests center on machine learning and data analytics for large social systems, including stochastic models and algorithms for graph and mobility processes, and recommender systems. He is also the current director of EPFL's Doctoral School in Computer and Communication Sciences.
From 2007-2010, he was with the Nokia Research Center (NRC) in Helsinki, Finland, serving as director of the Internet Laboratory, and driving a tech-transfer program focused on applied data mining and machine learning. In addition, he served on Nokia's CEO Technology Council, a technology advisory group reporting to the CEO. Prior to this, he was Assistant Professor at EPFL, and Principal Research Scientist in the Networking and Distributed Systems Laboratory at AT&T Research in New Jersey.
He received the 1998 Cor Baayen Award from the European Research Consortium for Informatics and Mathematics (ERCIM), and the 2006 CoNEXT/SIGCOMM Rising Star Award.