Skip to content
Open access

When Degree Anonymity Is Not Enough: Assessing Structural Re-identification Risk in Social Graphs

Oct 2026 · Anais do XIV Symposium on Knowledge Discovery, Mining and Learning (KDMiLe 2026) · 0 citations · 19 references

Abstract

Removing identifiers and equalizing node degrees do not guarantee graph privacy, as network topology acts as a structural quasi-identifier. Evaluating rather than assuming privacy, this article frames structural re-identification risk assessment as a reproducible evaluation problem and presents a configuration-driven pipeline that anonymizes graphs, validates anonymity, and reports privacy-utility metrics. We adopt the structural k-anonymity paradigm as our core design choice, evaluating it on Facebook Ego-Nets and Email-Enron across k ∈ {2, 5, 10, 20}. Under a 1-hop subgraph adversary (d = 1), effective protection reduces to degree-based anonymity: the 1-hop re-identification rate exceeds the degree-based rate by approximately 6× on Facebook and 38× on Enron at k = 2, indicating that neighborhoods can remain structurally distinguishable. We position this assessment relative to differential privacy (a difference of premises: publishing the whole graph versus releasing queries) and to stronger learned de-anonymization adversaries. Furthermore, increasing k does not improve privacy monotonically, as aggressive anonymization distorts degree distributions and shifts vulnerability patterns. Since our scenarios model basic adversaries, these risk rates represent lower bounds, indicating that graphs anonymized by degree-based protection should undergo structural risk assessment before publication.

Read PDF

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.