Robust GNN Watermarking via Implicit Perception of Topological Invariants
Jipeng Li · 2025
Read Robust GNN Watermarking via Implicit Perception of Topological Invariants by Jipeng Li (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-2510-25934.txt.
Introduction
Jipeng Li and Yannning Shen propose a watermark for graph neural networks that does not rely on a planted trigger. Graph neural networks learn from linked data, and they are valuable property that owners need to protect. Trigger based marks can break under common edits and can create doubt about who owns the model.
Their method, InvGNN-WM, ties ownership to how the model senses a graph invariant, a property that stays fixed under relabeling. A small head predicts algebraic connectivity on a private carrier set, and a decoder turns the output into bits. The mark kept clean accuracy, beat trigger and compression baselines, and survived pruning, fine tuning, and quantization, though plain distillation weakened it.
Catalog record
| CREATOR | Jipeng Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25934
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust GNN Watermarking via Implicit Perception of Topological Invariants Jipeng Li Abstract Graph Neural Networks (GNNs) are valuable intellectual property, yet most watermarks use backdoor triggers that break under common model edits and create ownership ambiguity. To tackle this challenge, we present InvGNN-WM , which ties ownership to a model’s implicit perception of a graph invariant, enabling trigger-free, black-box verification with negligible task impact. A lightweight head predicts normalized algebraic connectivity in an owner-private carrier set; a sign-sensitive decoder outputs bits, and a calibrated threshold τ ( α ) \tau(\alpha) controls the false-positive rate. Across diverse node and graph classification datasets and backbones, InvGNN-WM matches clean accuracy while yielding higher watermark accuracy than trigger- and explanation-based baselines. It remains strong under unstructured pruning, fine-tuning, and post-training quantization; plain knowledge distillation (KD) weakens the mark, while KD with a watermark loss (KD+WM) restores it. We provide guarantees for imperceptibility and robustness, and prove that exact removal is NP-complete. 1 Introduction Graph Neural Networks (GNNs) find applications in various domains, such as drug discovery, social networks, and recommendation ( Wu et al. 2021 ; Zhao et al. 2021 ; Gilmer et al. 2017 ; Xu et al. 2023 ; Hu et al. 2020 ) . As training depends on significant proprietary data, released models are valuable intellectual property and face the risks of redistribution and plagiarism ( Adi et al. 2018 ) . Although watermarking enables post-hoc verification, many GNN methods use trigger keys ( Zhang et al. 2021 ) : the model is trained to respond to graphs outside the task distribution \mathcal{D}_{\text{task}} (OOD). Fine-tuning, pruning, and distillation use only \mathcal{D}_{\text{task}} , so trigger-specific parameters get no preserving signal and drift or are pruned, weakening the mark ( Li et al. 2021 ) . OOD triggers also hinder black-box verification: owners must set a threshold without the impostor distribution on private triggers, causing unstable false-positive control ( Saha et al. 2022 ) . Similar issues arise in vision when a watermark is detached from normal inference ( Uchida et al. 2017 ) . To address the aforementioned concerns, we ask the following research question: Can ownership be tied to the same computation that solves the learning task, so that adding the watermark leaves utility essentially unchanged? We introduce InvGNN-WM , which binds ownership to a model’s implicit perception of a graph invariant. Concretely, the GNN learns to predict an invariant I(G) on owner-private carrier graphs; a lightweight head maps graph-level embeddings to an estimate of I(G) ; a separable sign-sensitive decoder turns the estimate into bits; and a calibrated threshold \tau(\alpha) sets the false-positive rate for black-box verification. Our theory and algorithms are stated for a generic permutation-invariant functional I(G) that admits a Lipschitz predictor and a separable sign-sensitive decoder; in experiments we instantiate I(G) with the normalized algebraic connectivity \tilde{\lambda}_{2} ( Fiedler 1973 ; Chung 1997 ) as a concrete and informative choice. Because expressive message-passing GNNs encode global structure ( Gilmer et al. 2017 ; Xu et al. 2023 ) , coupling ownership to invariant perception ties the mark to the model’s core logic rather than to exogenous patterns. On the theory side , we formalize a quantitative coupling between watermark removal and task degradation. We define a robustness margin on the carrier set that measures how far watermark scores lie from the decision boundary, and we summarize common edits—fine-tuning, unstructured pruning, and distillation—into a composite drift budget. Under a local Polyak–Łojasiewicz condition on the task loss and a Lipschitz bound on the perception head, any edit that is strong enough to flip watermark bits must exceed the margin and therefore incurs a nontrivial increase in task loss. In other words, successful removal provably trades off against utility. In complement, we also show that the watermark can be embedded with negligible task impact by choosing a small watermark weight and controlling the head’s sensitivity via spectral normalization ( Miyato et al. 2018 ) . The verification threshold is calibrated to a target false-positive level, and verification errors decay exponentially in the key length ( Hoeffding 1963 ; Janson 2004 ) . Finally, exact removal is NP-complete under our separable, sign-sensitive decoder, which explains why practical attacks resort to heuristic edits already covered by the margin analysis. Empirically , InvGNN-WM matches clean task accuracy across diverse node- and graph-classification datasets and backbones while delivering high watermark accuracy. The mark remains stable under unstructured pruning, fine-tuning, and post-training quantization; plain KD weakens the mark, while a simple KD with a watermark loss (KD+WM) restores it. Targeted “killshot” edits that collapse trigger-based designs have a limited effect on our invariant-coupled scheme. Contributions. (1) Method. InvGNN-WM ties ownership to a GNN’s implicit perception of a graph invariant, enabling trigger-free, black-box verification with minimal task impact. (2) Theory. We provide guarantees for imperceptibility and robustness, establish key uniqueness across independent carrier sets, and prove exact removal is NP-complete. (3) Evaluation. Across datasets and backbones, InvGNN-WM matches clean accuracy, achieves higher watermark fidelity than prior GNN watermarks, and remains reliable under pruning, fine-tuning, and quantization (with recovery under KD+WM). 2 Related Work Protecting the intellectual property (IP) of Graph Neural Networks (GNNs) ( Wu et al. 2021 ; Zhao et al. 2021 ) has drawn increasing attention, with digital watermarking emerging as a practical tool. Methods broadly fall into white-box and black-box settings. White-box methods embed watermarks into parameters or internal activations and require model access to verify ( Uchida et al. 2017 ; Zhang et al. 2018 ; Huang et al. 2023 ) ; they can be powerful but are impractical when only query access is available. Black-box methods aim to verify ownership via API queries and are therefore attractive for real-world deployment ( Adi et al. 2018 ; Zhang et al. 2018 ; Uchida et al. 2017 ; Bansal et al. 2022 ) . Backdoor-based watermarking for GNNs. The dominant black-box paradigm adapts backdoor ideas: train the model to react to a secret key set and later verify via predictions on those keys ( Adi et al. 2018 ) . For GNNs, Zhao et al. 2021 propose a random graph trigger for node classification, while Xu et al. 2023 extend to both node and graph classification and to inductive/transductive regimes. These approaches demonstrate high capacity and simple verification, yet inherit known weaknesses of backdoors: triggers are exogenous to task logic, enabling removal or attenuation by fine-tuning, pruning, and especially distillation-based laundering ( Li et al. 2021 ) . Beyond GNNs, a broader black-box watermarking literature explores multi-bit schemes, certified detection via randomized smoothing ( Bansal et al. 2022 ) , and robustness under distributional shifts. Function-integrated watermarking. A more recent line couples ownership to the model’s internal reasoning rather than to synthetic triggers. For GNNs, explanation-based watermarking links ownership to feature attributions of secret subgraphs ( Saha et al. 2022 ; Downer et al. 2025 ) , sidestepping data pollution and mitigating ambiguity. Outside GNNs, parameter- or representation-level embedding frameworks like Rouhani et al. 2018 (DeepSigns) and Le Merrer et al. 2019 (frontier stitching) aim to integrate watermarks with decision geometry, informing our design choices. 3 Preliminaries This section establishes the technical foundation for our work. We first define the notation for