DRGW: Learning Disentangled Representations for Robust Graph Watermarking

AI summary

Overview

Research area: Graph machine learning, specifically digital watermarking for graph-structured data, combining graph neural networks, invertible neural networks, and information-theoretic representation disentanglement.

Technical level: Advanced. The paper assumes familiarity with graph isomorphism networks, mutual information, invertible neural networks and change-of-variables Jacobians, and Neyman-Pearson hypothesis testing.

Scope: The paper proposes and empirically evaluates DRGW, a three-component framework for embedding and verifying a statistical watermark in graphs, tested on 18 real-world graphs across 6 categories and compared against two existing watermarking paradigms plus a deliberately weakened latent-space baseline.

What This Paper Is About

Graph data is widely shared across organizations, but there is no reliable way to prove where a leaked or misused graph came from. Existing graph watermarking either edits the graph's discrete topology directly (making the mark fragile) or hides it inside holistic graph embeddings (where the watermark becomes entangled with utility-relevant information and can be discarded when the embedding is converted back into a discrete graph). DRGW's goal is to embed a watermark that stays recoverable after attacks, while leaving the graph's structure and downstream usefulness essentially unchanged, by learning separate representations for "structure" and "watermark."

Key Contributions

1. A disentanglement-based watermarking framework. The authors propose DRGW, described as the first graph watermarking framework that addresses information entanglement through disentangled representation learning. It learns an invariant structural representation while deriving a statistically independent, orthogonal watermark carrier, so watermark operations are isolated from the graph's core functional properties.

2. A graph-aware INN for high-fidelity watermark transformation. A conditional invertible neural network transforms the watermark carrier, conditioned on the structural representation, providing a lossless channel for embedding and extraction and confining perturbations to a minimal subspace.

3. A structure-aware editor for controllable discretization. The editor translates the continuous watermarked carrier into a discrete edit plan (a budgeted set of edge flips) rather than reconstructing the graph, specifically to counter the "discretization-induced watermark degradation" that causes standard graph decoders to discard the watermark.

4. An extensive empirical evaluation. Experiments on 18 real-world graphs in 6 categories against a structure-space method (Towards), a latent-space method (KGMark), and a Naive Latent-Space Baseline, measuring detectability (AUC), robustness under attacks, and transparency (structural and functional fidelity).

Main Findings

• Near-perfect clean detectability. On unattacked graphs, DRGW achieves an AUC of 0.998 or higher in every dataset category: 0.999 on Social Networks, 0.998 on Web Graphs, 0.999 on Academic Networks, 0.999 on Knowledge Graphs, 0.999 on E-commerce & Recommendation, and 0.998 on Road Networks.

• The naive baseline is deceptively strong when clean but collapses under attack. The Naive Latent-Space Baseline reaches 0.997 clean AUC on Social Networks, yet its AUC falls to 0.598 under a 50% edge flip on Social Networks, described as barely better than random guessing, because its reconstruction-oriented decoder cannot distinguish the faint watermark from attack-induced noise.

• The structural-space method fails on regular topologies. Towards achieves an AUC of 0.981 on Social Networks but only 0.520 on Road Networks, which the authors attribute to its reliance on specific subgraph patterns that are absent in grid-like graphs. Its latent-space adversarial attack results are marked "-" because those attacks were not applicable to the structure-space methodology.

• Robustness under severe perturbation. Under 50% node deletion on Academic Networks, DRGW maintains a 0.970 AUC. Its AUC under 50% edge flip is 0.962 on Social Networks, 0.959 on Web Graphs, 0.970 on Academic Networks, 0.964 on Knowledge Graphs, 0.958 on E-commerce & Recommendation, and 0.932 on Road Networks.

• Order-of-magnitude transparency improvements. On Social Networks, DRGW reduces the link prediction performance drop to 0.72%, roughly a 75% reduction relative to the 2.85% drop of the Naive Baseline (KGMark: 2.35%; Towards: 4.13%). DRGW also reports 0.72% (Web Graphs: 1.04%; Academic: 0.68%; Knowledge Graphs: 0.70%; E-commerce: 0.81%; Road Networks: 2.45%, versus KGMark's 5.30% and the Naive Baseline's 5.80% on Road Networks).

• Low structural distortion. DRGW's Flipped Edges (%) is 0.058 on Social Networks (Naive Baseline 0.101, KGMark 0.087), and its Cosine Similarity of node embeddings is 0.993 on Social Networks versus 0.965 for the Naive Baseline and 0.970 for KGMark. On Road Networks its Assortativity distortion is 1.85% versus 5.82% (KGMark) and 6.25% (Naive Baseline).

• A predictable transparency-robustness trade-off. A sensitivity analysis varying watermark strength (α) and editing budget (k) found that fidelity loss increases smoothly and monotonically with both, while robustness reaches a plateau of near-optimal performance with diminishing returns. The authors report a wide "sweet spot" and set the defaults at α = 0.1 and k = 0.1%.

• Ablation results are not reported in the available content. The paper announces an ablation study for causal analysis, but the provided text is truncated immediately after the sentence introducing it, so the ablation figures and conclusions are not included.

Methodology in Plain English

Split the graph into two cleanly separated summaries. An encoder built on a Graph Isomorphism Network (chosen for its expressiveness and permutation invariance) produces two representations: an invariant structural representation (h_s) that captures the graph's durable topology, and a watermark carrier (h_w). The authors motivate the split with the data processing inequality, which bounds how much the watermark can affect utility by the mutual information between the two representations. They enforce the separation with two losses: a contrastive invariance loss that keeps h_s stable across perturbed variants of the graph (random node dropping, edge addition or deletion), and an orthogonality loss between the batch representation matrices as a proxy for statistical independence.

Put the watermark through a reversible, structure-conditioned channel. Because detectability is bounded by signal integrity, the transformation applied to the carrier must be invertible. The Graph-aware INN is a stack of coupling layers where one part of the input is left unchanged and the other is affinely transformed by parameters from a GCN conditioned on h_s. It is trained with a negative log-likelihood objective including the log-determinant Jacobian term. The watermark is injected in the latent space by shifting the mapped carrier: z_w = f_INN(h_w; h_s) + αw, with α controlling embedding strength; the inverse maps z_w back to a modified carrier.

Convert the continuous signal into a small number of discrete edits. Instead of using a reconstruction-oriented decoder, a structure-aware editor scores candidate edges (all existing edges plus a random sample of non-edges) with an MLP over the concatenated structural and carrier representations of both endpoints. The top-k scores form a binary mask that flips those edges, producing the edit plan ΔE and the watermarked graph.

Verify with a statistical test rather than an ad-hoc rule. Because the INN maps unwatermarked carriers to a standard Gaussian prior, the null hypothesis is z_test ~ N(0, I) and the alternative is z_test ~ N(α′w, I) with α′ ≤ α accounting for attack degradation. By the Neyman-Pearson lemma the most powerful test is a likelihood ratio test, which simplifies for these Gaussian means to a matched filter: the inner product of the extracted latent and the watermark. The test statistic is Gaussian under both hypotheses, and a user-chosen false positive rate β yields the threshold τ = ||w|| · Φ⁻¹(1 − β), equivalently a p-value compared against β.

Why This Matters

Research impact. The paper positions representation disentanglement as a solution to the core problems of graph watermarking — information entanglement and discretization loss — claiming the first use of disentanglement specifically in the watermarking context, which creates a new intersection between two previously separate lines of work. It also reframes watermark verification as a formal hypothesis test with a controllable false-positive rate, rather than a heuristic threshold.

Real-world applications.

• Provenance tracking for shared social network or web graph data, so a leak can be traced to a specific recipient.
• Copyright enforcement and licensing audits for knowledge graphs and recommendation/e-commerce interaction graphs sold or exchanged between organizations.
• Integrity verification of map and road network data, where the paper specifically shows that prior structure-space watermarking collapses to random guessing.
• Ownership dispute resolution, where the p-value framework provides quantifiable confidence and bounds the risk of falsely accusing a party.

Industry relevance. Organizations that monetize or share graph-structured assets — data marketplaces, recommender-system vendors, mapping providers, and web platforms — need attribution mechanisms that survive data cleaning and perturbation pipelines while leaving downstream model accuracy intact. DRGW's reported transparency numbers (link prediction drops below 1% on five of six categories) and the fact that verification parameters are frozen and publicly shared are directly relevant to deployment, because third parties can run verification without holding the owner's model weights.

Future Directions

• Complete and report the ablation study. The paper announces a causal ablation of its components but the results are not present in the available content; isolating the contribution of the disentangled encoder, the INN, and the editor remains the key open empirical question.

• Broaden the adaptive attack suite. The evaluation covers edge flips, node deletion, isomorphism variation, and two adaptive attacks (NEA and the L2 Metric attack). Whether the watermark survives threshold-aware or disentanglement-aware adversaries that specifically target the structural anchor is untested.

• Scale and cost of the editor. The scoring procedure evaluates all existing edges plus a random sample of non-edges, so how the approach behaves on graphs much larger than the 18 benchmark datasets, and whether the sampling introduces variance in detection, is not established.

• Automatic selection of α and k. The sensitivity analysis describes a "sweet spot" but the default values are fixed at α = 0.1 and k = 0.1%. Whether these can be chosen adaptively per graph from measurable structural properties is left open.

Target Audience

Researchers and graduate students working on graph representation learning, digital watermarking, data provenance, and intellectual property protection for machine learning data. It is also relevant to security and privacy researchers interested in information-theoretic disentanglement and hypothesis-testing-based verification, and to engineers at organizations that distribute graph datasets and need an auditable ownership mechanism. Readers should be comfortable with GNN architectures, invertible neural networks, and basic statistical testing; the paper's claims are empirical and the appendices containing dataset statistics, hyperparameters, metric definitions, sensitivity heatmaps, and carrier visualizations are referenced but not included in the available text.

Authors’ abstract

Graph-structured data is foundational to numerous web applications, and watermarking is crucial for protecting their intellectual property and ensuring data provenance. Existing watermarking methods primarily operate on graph structures or entangled graph representations, which compromise the transparency and robustness of watermarks due to the information coupling in representing graphs and uncontrollable discretization in transforming continuous numerical representations into graph structures. This motivates us to propose DRGW, the first graph watermarking framework that addresses these issues through disentangled representation learning. Specifically, we design an adversarially trained encoder that learns an invariant structural representation against diverse perturbations and derives a statistically independent watermark carrier, ensuring both robustness and transparency of watermarks. Meanwhile, we devise a graph-aware invertible neural network to provide a lossless channel for watermark embedding and extraction, guaranteeing high detectability and transparency of watermarks. Additionally, we develop a structure-aware editor that resolves the issue of latent modifications into discrete graph edits, ensuring robustness against structural perturbations. Experiments on diverse benchmark datasets demonstrate the superior effectiveness of DRGW.