Cluster-Aware Attacks on Graph Watermarks

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.

Accepted at ESORICS 2026