# Robust GNN Watermarking via Implicit Perception of Topological Invariants

arXiv: https://arxiv.org/abs/2510.25934 · HTML: https://mlsanity.com/paper/2510.25934/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 27 references that are in the map.
- First posted on arXiv 29 Oct 2025.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Turning Your Weakness Into a Strength: Watermarking Deep Neural Networks by Backdooring](https://mlsanity.com/paper/1802.04633/) (2018)
- [Embedding Watermarks into Deep Neural Networks](https://mlsanity.com/paper/1701.04082/) (2017)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Adversarial Frontier Stitching for Remote Neural Network Watermarking](https://mlsanity.com/paper/1711.01894/) (2017)
- [Certified Neural Network Watermarks with Randomized Smoothing](https://mlsanity.com/paper/2207.07972/) (2022)
- [Neural Network Laundering: Removing Black-Box Backdoor Watermarks from Deep Neural Networks](https://mlsanity.com/paper/2004.11368/) (2020)
- [Watermarking Graph Neural Networks based on Backdoor Attacks](https://mlsanity.com/paper/2110.11024/) (2021)
- [Watermarking Graph Neural Networks via Explanations for Ownership Protection](https://mlsanity.com/paper/2501.05614/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are valuable intellectual property, yet many watermarks rely on backdoor triggers that break under common model edits and create ownership ambiguity. 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 on an owner-private carrier set; a sign-sensitive decoder outputs bits, and a calibrated threshold 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 compression-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 we prove that exact removal is NP-complete.