Network Structure and Privacy - The Re-Identification Risk in Graph Data

Explore the critical privacy vulnerabilities inherent in graph data structures through this 10-minute conference talk from PEPR '25. Examine how network connections themselves can serve as unique identifiers that compromise user anonymity, even when traditional anonymization techniques are applied. Learn about the relationship between a network's average degree and the risk of node re-identification based solely on structural patterns. Discover how an individual's local network neighborhood creates distinctive fingerprints that can be exploited for privacy attacks. Understand the challenges of effectively anonymizing graph data representing human connections and relationships. Gain insights into designing privacy-aware data collection and anonymization methods that balance the benefits of data sharing with robust individual privacy protection. Presented by researchers from the Technical University of Denmark and Aalto University, this talk provides essential knowledge for data scientists, privacy researchers, and anyone working with network data who needs to understand and mitigate re-identification risks in graph structures.