Cluster-Aware Attacks on Graph Watermarks

Alexander Nemecek, Emre Yilmaz, Erman Ayday · 2025

Read Cluster-Aware Attacks on Graph Watermarks by Alexander Nemecek, Emre Yilmaz, Erman Ayday (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17971.txt.

Introduction

Alexander Nemecek, Emre Yilmaz, and Erman Ayday test attacks that target community structure in watermarked graph data. Their 2025 paper notes that shared graph sets, from social to medical data, carry hidden marks so leaks can be traced. Past safety tests only threw random edge changes at those marks, a weak foe.

Cluster-aware attacks use community finders to guide edits: thicken inside groups while cutting their borders, or thin inside while adding cross noise. Across real data sets and mark schemes, the guided attacks beat random ones. Credit for a leak fell, at like levels of graph damage. Current marks look exposed, and defenses must plan for foes who read group structure.

Catalog record

CREATORAlexander Nemecek, Emre Yilmaz, Erman Ayday
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-17971

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cluster-Aware Attacks on Graph Watermarks Alexander Nemecek, Emre Yilmaz, Erman Ayday 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. Our code is available at https://github.com/ANCP2021/Cluster-Aware-Graph-Watermarking-Attacks . 1 Introduction Many datasets are structured as graphs, representing relationships in many domains, including social networks [ 21 ] , biomedical research [ 12 ] , and cryptographic applications [ 1 ] . These graphs often contain sensitive information, making their secure storage, sharing, and analysis a concern. Researchers and organizations frequently share graph-structured data with trusted parties for collaborative analysis and real-world applications. However, the sensitive nature of this data raises security and privacy risks, including unauthorized access and data leakage among distributed entities. To mitigate these threats, data owners must ensure their datasets remain protected against adversarial modifications and that any unauthorized redistribution can be attributed to its source. Watermarking, the process of embedding a detectable signature within an object, has been widely studied across multiple domains, including imaging [ 17 ] , audio [ 2 ] , databases [ 7 ] , and machine learning models [ 14 , 23 ] . Graph-structured data is no exception; in a graph watermarking, signatures are embedded through structural modifications [ 24 , 6 ] or spectral transformations [ 4 ] , enabling ownership verification and unauthorized redistribution detection. However, despite advances in embedding techniques, the robustness evaluation of these schemes remains limited. Specifically, existing work primarily evaluates robustness against random edge perturbation attacks, failing to consider more sophisticated, structure-aware adversaries. Real-world graphs typically exhibit community structure, where nodes naturally form densely connected subgroups (clusters). An adversary who recognizes these structures can develop targeted attack strategies that selectively modify edges within or between clusters to compromise graph watermark integrity more effectively than random edge modifications. This structural vulnerability is independent of the watermarking technique employed: both structural and spectral approaches rely on preserving statistical properties that community-aware perturbations can disrupt. Such adversaries are not hypothetical, as an insider at a recipient organization with only simple network science knowledge can run community detection on a leaked graph using freely available libraries (e.g., NetworkX or igraph), with no access to the watermarking system or feedback from it. Analogous structure-aware strategies are already documented in adjacent literature, where community-guided perturbations degrade graph neural networks more effectively than random baselines [ 5 ] . Despite this low barrier to entry and documented precedent, no existing work evaluates watermarking robustness against cluster-aware adversaries. All prior schemes are evaluated exclusively against random edge perturbations, leaving data owners with a false sense of attribution guarantees against a realistic class of adversaries. The goal of this work is to address the gap in existing literature by introducing the first systematic evaluation of cluster-aware attacks on graph watermarking. We present a threat model in which adversaries leverage community detection algorithms to guide strategic edge modifications, and we demonstrate that such attacks are more effective than random baselines across multiple graph datasets and clustering algorithms. Our key contributions can be summarized as follows: 1. Cluster-Aware Threat Model : We introduce a novel adversarial model in which attackers exploit graph community structure through two strategic approaches: intra-cluster densification with inter-cluster boundary removal, and intra-cluster sparsification with inter-cluster noise injection. 2. Evaluation Across Watermarking Paradigms : We evaluate cluster-aware attacks against both structural [ 24 ] and spectral [ 4 ] watermarking schemes, demonstrating that vulnerability to structure-aware adversaries generalizes across embedding strategies. 3. Parameter-Free Clustering Analysis : We evaluate four parameter-free community detection algorithms, providing the first systematic analysis of clustering method effectiveness for adversarial graph perturbation under realistic black-box conditions. 4. Empirical Findings : Across three real-world graphs with varying structural properties and both watermarking paradigms, we show that cluster-aware attacks reduce attribution accuracy compared to random edge flipping while introducing comparable structural distortion across most configurations, demonstrating superior attack efficiency. As graph-based data becomes increasingly critical to both the academic community and industry, ensuring the ability to trace and protect such data against evolving attack strategies is paramount. Our findings suggest that current watermarking schemes, evaluated solely against random perturbations, remain vulnerable to structure-aware adversarial behavior. By addressing these gaps, we aim to establish a more robust benchmark for future graph watermarking designs. 2 Background and Related Work In this section, we review the background on graph watermarking schemes, community detection in graphs, and existing threat models evaluated in prior work. 2.1 Graph Watermarking Graph watermarking is a subfield of digital watermarking that focuses on embedding detectable signatures within graph-structured data to enable ownership verification and unauthorized redistribution detection. The process transforms an original graph G into a watermarked version G^{\prime} by embedding a user-specific signature that can be extracted and verified from a potentially modified graph \hat{G} , even after adversarial perturbations. Despite the increasing importance of graph-structured data, research on graph watermarking remains relatively limited. To the best of our knowledge, only three watermarking schemes have been proposed in the literature: Zhao et al. [ 24 ] , Eppstein et al. [ 6 ] , and Bourrée et al. [ 4 ] . These schemes can be broadly categorized into two classes based on their embedding approach: structural , which modify graph topology directly, and spectral , which embed watermarks in the frequency domain of the graph’s adjacency matrix. Structural watermarking schemes embed signatures by directly modifying the topology of the graph through edge modifications. These methods typically select a subset of nodes and edges in the original graph G and transform their local structure to encode a watermark pattern. The key principle is to create detectable topological features that can be regenerated and verified using a secret key, while minimizing distortion to the graph’s global properties. The most widely recognized structural graph watermarking scheme, proposed by Zhao et al., embeds a randomly generated Erdős-Rényi subgraph watermark W into the original graph G by selecting k nodes based on Node Structure Descriptors (NSDs) 1 1 1 A Node Structure Descriptor is a structural signature of a node defined as a sorted array of its neighbors’ degrees.

Read the complete text