When One View Is Not Enough: Joint De-anonymization of Temporal Social Networks

Social network de-anonymization refers to the process where an adversary recovers user identities by mapping an anonymized network to a correlated real-name network, and has attracted research interests due to the growing privacy concerns. Prior art usually assumes that the adversary observes a single pair of correlated networks. However, real-world social networks naturally evolve, thus enabling the adversary to obtain correlated observations across snapshots. Although recent studies highlight the increased privacy risk in this temporal context, quantitative theory on how multi-snapshot observations affect the feasibility of de-anonymization remains unexplored.To address this, we investigate joint de-anonymization of temporal social networks. Given a social network modeled as a general random graph evolving over time, our goal is to map the anonymized users observed across multiple snapshots to their real identities. Specifically, we aim to answer two fundamental questions: (i) When is perfect joint de-anonymization possible? (ii) How to efficiently find the true mapping? To this end, we first theoretically establish both necessary and sufficient conditions for perfect joint de-anonymization, revealing a critical insight: leveraging multi-snapshot observations enables accurate user re-identification even if individual snapshots alone are insufficient. Then, by casting joint de-anonymization as a generalized quadratic assignment problem, we design efficient polynomial-time algorithms to approximate the true mapping based on convex relaxation and Frank-Wolfe optimization. Finally, extensive experiments on synthetic and real social networks validate our theoretical findings and the proposed algorithms.