Privacy-preserving computation on graph-structured data

Abstract

There are many examples of graph-structured data, like records of friendships in social networks, travel patterns in transport networks and communications meta-data in telecommunication networks, and many more. In such data, people are represented as nodes and their interactions as edges. Graphs can provide valuable information about people and their connections, however privacy disclosure of performing or releasing graph analysis is a major open challenge. Naive techniques such as anonymisation on edges and nodes have been shown to fall short: heuristically anonymised graphs still leak significant structural information that can be used to match individuals and recover sensitive information..