The Right to Hide: Masking Community Affiliation via Minimal Graph Rewiring
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911141963235328 |
|---|---|
| author | Silvestri, Matteo Gabrielli, Edoardo Silvestri, Fabrizio Tolomei, Gabriele |
| author_facet | Silvestri, Matteo Gabrielli, Edoardo Silvestri, Fabrizio Tolomei, Gabriele |
| contents | Protecting privacy in social graphs may require obscuring nodes' membership in sensitive communities. However, doing so without significantly disrupting the underlying graph topology remains a key challenge. In this work, we address the community membership hiding problem, which involves strategically modifying the graph structure to conceal a target node's affiliation with a community, regardless of the detection algorithm used. We reformulate the original discrete, counterfactual graph search objective as a differentiable constrained optimisation task. To this end, we introduce $\nabla$-CMH, a new gradient-based method that operates within a feasible modification budget to minimise structural changes while effectively hiding a node's community membership. Extensive experiments on multiple datasets and community detection methods demonstrate that our technique outperforms existing baselines, achieving the best balance between node hiding effectiveness and graph rewiring cost, while preserving computational efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00432 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Right to Hide: Masking Community Affiliation via Minimal Graph Rewiring Silvestri, Matteo Gabrielli, Edoardo Silvestri, Fabrizio Tolomei, Gabriele Social and Information Networks Protecting privacy in social graphs may require obscuring nodes' membership in sensitive communities. However, doing so without significantly disrupting the underlying graph topology remains a key challenge. In this work, we address the community membership hiding problem, which involves strategically modifying the graph structure to conceal a target node's affiliation with a community, regardless of the detection algorithm used. We reformulate the original discrete, counterfactual graph search objective as a differentiable constrained optimisation task. To this end, we introduce $\nabla$-CMH, a new gradient-based method that operates within a feasible modification budget to minimise structural changes while effectively hiding a node's community membership. Extensive experiments on multiple datasets and community detection methods demonstrate that our technique outperforms existing baselines, achieving the best balance between node hiding effectiveness and graph rewiring cost, while preserving computational efficiency. |
| title | The Right to Hide: Masking Community Affiliation via Minimal Graph Rewiring |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2502.00432 |