A graph neural network (GNN) is a model that classifies a node or a whole graph by repeatedly mixing each node's features with its neighbours'. Deployed GNNs increasingly return an explanation alongside each prediction, typically a score per node saying how much it mattered. Recent work shows these scores let an attacker copy both the model and its reasoning. We propose a defence borrowed from graph privacy. The service releases scores only at a coarser structural resolution, so that every reported score is shared by at least $k$ nodes that look structurally alike, for example nodes with the same degree. Under this rule the attacker learns which kinds of structural positions matter. It no longer learns which specific atoms or edges carry the decision.
The idea comes from $k$-degree anonymity, the rule that every node in a published graph must share its degree with at least $k-1$ others (Personalized Privacy Protection in Social Networks). That rule was built to stop re-identification of people in released social networks. We apply it to the explanation instead of the data. The central question is empirical. At equal loss of explanation faithfulness, does tying scores to structural equivalence classes hurt explanation-guided stealing more than the obvious cheaper option of rounding scores into a few tiers? If it does not, the rounding option wins and we will say so.
Core Claim
The motivating attack is EGSteal (How Explanations Leak the Decision Logic: Stealing Graph Neural Networks via Explanation Alignment). It trains a copy model, the surrogate, with two tools. The first is a pairwise ranking loss that makes the surrogate's node-importance ordering match the victim's. The second creates free training graphs by deleting nodes the explanation marks as unimportant, on the assumption that the label does not change. On NCI1 it reaches 42.38% rank correlation between surrogate and victim explanations, against 15.22% for a plain teacher-student copy trained on labels. Both tools depend on fine-grained, per-node distinctions.
Our observation is that a message-passing GNN already assigns identical internal representations to nodes that the Weisfeiler–Lehman (WL) procedure cannot tell apart. WL is the standard test that iteratively recolours each node by the multiset of its neighbours' colours. As a result, class-activation explanations such as Graph-CAM are already constant within the WL classes at the model's depth $L$. The natural explanation is therefore "structurally anonymous" at a resolution of roughly $L$ hops. The trouble is that these classes are tiny in molecules, often a single atom, so the explanation pins down exact locations.
Our defence releases scores that are constant on a coarser partition $\mathcal{P}$ of the nodes. The coarsest meaningful case is the depth-1 WL partition, which is simply degree plus node type; this is exactly the partition $k$-degree anonymity protects. Classes of $\mathcal{P}$ smaller than $k$ are merged, and for each graph we release the most faithful such score vector:
$$ \hat{s} = \arg\min_{s' \in \mathcal{S}_{\mathcal{P},k}} \; \| s - s' \|_2^2 , $$
Here $s$ is the victim's true per-node score vector. $\mathcal{S}_{\mathcal{P},k}$ is the set of score vectors that are constant on every class of $\mathcal{P}$, where every class has at least $k$ nodes. With the partition fixed, the solution is the within-class average. The research content lies in choosing the partition: its WL depth, and how undersized classes are merged so that faithfulness to the model's prediction is lost as little as possible.
This produces a single dial running from exact explanations (depth $L$, no merging) to $k$-degree-anonymous explanations. The claim is that the dial yields a better tradeoff between faithfulness and stealing resistance than dials that ignore structure.
Relation to Prior Work
Three works motivate the gap. EGSteal supplies the attack and our evaluation protocol, and it proposes no defence. Two tabular studies show that explanations expose decision boundaries directly. From Counterfactuals to Trees copies decision trees exactly from counterfactual thresholds. Exploring Counterfactual Explanations Through the Lens of Adversarial Examples shows counterfactuals and adversarial examples follow nearly the same optimisation path, with Spearman correlation above 0.90. Neither addresses graphs or defences.
Two works supply design constraints. XRand (XRand: Differentially Private Defense against Explanation-Guided Attacks) randomises tabular feature rankings under local differential privacy. It cut backdoor attack success on EMBER from 77.8% to 10.2% at $\epsilon=1$. It targets backdoors rather than model copying, and its noise ignores graph structure. D4Explainer (D4Explainer: In-distribution Explanations of Graph Neural Network via Discrete Denoising Diffusion) shows that arbitrary perturbations of graph explanations drift away from the kind of graphs the model was trained on. That warns against naive noise on graph objects. Our class-averaged scores never alter the graph, so they avoid this problem.
Two strands supply the method. The structural-anonymity literature provides the equivalence notions: $k$-degree, $k$-automorphism (Privacy-Preserved Network Data Publishing), and $k$-symmetry (Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation). All of these were applied to published data, never to model outputs. k-Anonymous Decision Tree Induction is the closest precedent in spirit. It builds the anonymity constraint into the transparent artefact rather than preprocessing the data, and it beats anonymize-then-mine by 0.6 to 3 points of error. It covers only tabular trees.
We do not claim to stop label-only theft. On Stealing Graph Neural Network Models copies GNNs with 91% accuracy from 100 queries on Physics using labels alone. Our goal is narrower: remove the extra advantage that explanations provide, which covers both the victim's reasoning and the accuracy gain above label-only copying.
Research Program
The program has three parts.
The first is a short analysis. We will state and verify the lemma that Graph-CAM-style scores of an $L$-layer message-passing GNN are constant on depth-$L$ WL classes. We will then show that optimisation-based explainers, such as the edge masks of CF-GNNExplainer, can break these ties arbitrarily. When they do, they reveal a tie-breaking distinction the model itself does not make. This addresses the file's open question about faithfulness under symmetry: a faithful explainer must respect the model's own symmetries, so breaking them is pure leakage.
The second part builds the release mechanism. It computes WL partitions at each depth from $L$ down to 1. It then merges undersized classes greedily, choosing at each step the merge that least reduces fidelity+ and fidelity−. Fidelity+ and fidelity− measure how much the prediction changes when the highlighted nodes are removed or kept.
The third part attacks our own defence. We will build an adaptive EGSteal that knows the partition. It can train its surrogate so that class-averaged surrogate scores match the released ones. It can also sample within-class node subsets when making its augmented graphs. Without this adaptive attacker, any gain from the defence would not be credible.
Baselines
The do-nothing reference is EGSteal against unmodified Graph-CAM explanations. It is re-run with the released code (EGSteal repository) on the same victim models, splits and query budgets. The reported NCI1 figures of 42.38% rank correlation for EGSteal and 15.22% for teacher-student fix our sanity check. The teacher-student copy trained on labels only serves as the floor. A defence cannot usefully push the attacker below that level, and approaching it is the target.
The strongest existing defence is XRand-style randomised response over node rankings. We will port it from feature rankings to node rankings and tune its privacy budget over a grid. It stands in for the only published explanation-guided defence in the file.
The ablation that decides the proposal is tier quantisation. It rounds scores into the same number of distinct levels as our partition produces, with the level boundaries chosen to maximise faithfulness. This makes the two methods equal in how much information they reveal and different only in whether ties follow structure or follow score value. A second ablation uses a random partition with the same class-size profile. It tests whether any tying helps or whether structural tying specifically helps.
Every method gets the same victim models and the same query budget. Every method also gets the same tuning grid, set so that each reaches the same faithfulness levels: fidelity+ within 5%, 10% and 20% of the unmodified explainer. We then compare attacker success at matched faithfulness. Beating a baseline means lower surrogate rank correlation and lower agreement between surrogate and victim predictions, at every matched faithfulness level, averaged over five seeds, with non-overlapping confidence intervals. The comparison must hold against the adaptive attacker as well as the standard one.
Why not just…?
Why not just add differential-privacy noise to the scores? EGSteal uses only relative order, so the noise must be large enough to scramble rankings everywhere. XRand needed a per-query optimisation even for tabular vectors. Noise also spends its disruption uniformly, including on the obviously irrelevant majority of nodes. We expect it to lose more faithfulness per unit of damage to the attacker. The frontier comparison measures this directly rather than assuming it.
Why not just round scores into a few tiers? This is the real threat, and it is why tier quantisation is the central ablation. Tiers also create ties. Our hypothesis is that tier boundaries still separate nodes inside a structural class. The attacker would then still learn which specific atom in a symmetric-looking region matters, which is exactly the signal the style-node augmentation needs. Structural tying removes that signal by construction. If matched-level quantisation reaches the same frontier as our method against the adaptive attacker, we will conclude the structural ingredient is unnecessary and report quantisation as the recommended defence.
Why not just release labels only? Label-only APIs fail regulatory and user needs for explanations. They also do not stop theft, given the 100-query result on Physics in On Stealing Graph Neural Network Models. The meaningful question is how much of the explanation's extra leakage can be removed while an explanation is still released.
Why not just anonymize the training graph? The attacker's leverage comes from per-query explanations of new graphs. Anonymizing the training data does not constrain those. The kADET results also suggest that task-blind preprocessing costs accuracy.
Proposed Experiments
The main experiments cover graph classification on NCI1, NCI109, Mutagenicity and AIDS, following EGSteal's setup including the AIDS-to-NCI109 transfer. They also include BA-3Motif, a synthetic dataset with known ground-truth motifs, run through the D4Explainer codebase (D4Explainer code).
Attacker metrics are surrogate–victim explanation rank correlation, prediction agreement, and surrogate accuracy. Defender metrics are fidelity+, fidelity−, and, on BA-3Motif, the fraction of ground-truth motif nodes placed in the top-scored classes. The BA-3Motif metric is a proxy for whether a human could still see the right structure.
The decisive result is a faithfulness-versus-leakage frontier for each $k$ in {2, 4, 8} and each WL depth. Structural tying must dominate matched-level quantisation and random partitioning against the adaptive attacker, and it should lower rank correlation substantially toward the 15.22% teacher-student floor on NCI1. For XRand-style noise on graphs, no reported result was found on Lacuna, so we will measure it.
A secondary check covers node classification on BA-Shapes and Tree-Cycles, where CF-GNNExplainer reports at least 94% counterfactual accuracy with 1.47 to 2.39 edges removed on average. There we will test whether $k$-degree-tied edge scores keep counterfactual recourse usable, and whether they reduce how precisely the released explanations reveal the victim's decision boundary.
References
- Personalized Privacy Protection in Social Networks
- How Explanations Leak the Decision Logic: Stealing Graph Neural Networks via Explanation Alignment
- From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks
- Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis
- XRand: Differentially Private Defense against Explanation-Guided Attacks
- D4Explainer: In-distribution Explanations of Graph Neural Network via Discrete Denoising Diffusion
- Privacy-Preserved Network Data Publishing
- Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation
- k-Anonymous Decision Tree Induction
- On Stealing Graph Neural Network Models
- CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks