Abstract:Graph-structured datasets are increasingly central to sensitive applications spanning social networks, biomedical research, and cryptographic systems. As organizations share these datasets with trusted parties for collaborative analysis, protecting against unauthorized redistribution becomes critical. Graph watermarking addresses this challenge by embedding detectable signatures that enable ownership verification and attribution of leaked data. However, despite advances in watermarking techniques, existing robustness evaluations remain limited to random edge perturbation attacks, overlooking more sophisticated adversaries who exploit community structure present in real-world graphs. We introduce the first systematic evaluation of cluster-aware attacks on graph watermarking schemes. We present a threat model in which adversaries leverage community detection algorithms to guide strategic edge modifications, targeting either intra-cluster densification with inter-cluster boundary removal, or intra-cluster sparsification with inter-cluster noise injection. Evaluating against representative structural and spectral watermarking schemes, we demonstrate that cluster-aware attacks outperform random perturbations across real-world datasets and clustering algorithms. Our findings reveal that cluster-aware attacks reduce attribution accuracy while introducing structural distortion comparable to random attacks in most configurations, demonstrating superior attack efficiency. These results establish that current watermarking schemes, evaluated solely against random perturbations, remain vulnerable to structure-aware adversarial behavior, highlighting the need for robust defenses that account for community-exploiting adversaries in graph-based systems.
From: Alexander Nemecek [view email]
[v1]
Thu, 24 Apr 2025 22:49:28 UTC (156 KB)
[v2]
Wed, 11 Mar 2026 16:39:19 UTC (196 KB)
[v3]
Mon, 17 Aug 2026 21:42:08 UTC (201 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。