Robust GNN Watermarking via Implicit Perception of Topological Invariants

Abstract

Graph Neural Networks (GNNs) represent valuable intellectual property, yet watermarks based on out-of-distribution triggers can weaken under pruning, fine-tuning, and distillation. We present InvGNN-WM, which links ownership verification to graph-invariant prediction. By supervising a shared GNN backbone to predict normalized algebraic connectivity on owner-private carrier graphs, InvGNN-WM enables calibrated multi-bit black-box verification through either an auxiliary scalar endpoint or a fixed owner-side decoder of ordinary task logits. We provide conditional guarantees for task-loss control, decision preservation, and key separation, and prove NP-completeness of the exact-removal decision problem for a restricted class of monotone separable decoders. Experiments on node- and graph-classification benchmarks demonstrate high watermark fidelity with small changes in task performance. The task-logit deployment achieves higher detection rates than PreGIP-adapted in matched comparisons and retains detection under the evaluated extraction and retraining budgets. Watermark-assisted distillation further enables owner-side recovery using private verification material.