G2TA: Converting Graph Data to Table Data for Employing Deanonymization Attacks
摘要
The widespread sharing of anonymized graph datasets for research and public use has raised new privacy concerns, as sensitive information can often be re-identified through advanced deanonymization techniques. Existing graph deanonymization methods span a variety of strategies, including structural alignment, embedding-based matching, and feature extraction combined with machine learning classifiers. However, these approaches remain grounded in graph-specific workflows. In this paper, we introduce G2TA (Graph to Table Attack), a novel attack framework that bridges graph and tabular privacy domains. By transforming anonymized graphs into semantically enriched tabular representations that capture structural patterns and neighborhood-level attribute signals, our approach enables the use of record linkage and quasi-identifier-based attacks originally developed for tabular datasets. These semantic features preserve node-to-neighborhood relationships that are crucial for identity recovery. We evaluate the framework on anonymized graphs and compare it to well-known graph-based attacks, showing that meaningful re-identification is possible, even without graph-specific algorithms. We also evaluated our methodology on differentially private graphs. Our findings underscore the importance of privacy evaluations that account for both graph-specific threats and relational tabular attacks before public release.