Discharging Attribution Mass to Localize Graph Backdoor Triggers

Graph neural networks (models that classify a molecule or a network by passing messages along its edges) can be backdoored. An attacker plants a small subgraph, the "trigger," in some training graphs, and the model learns to output the attacker's label whenever that subgraph appears. The leading defenses ask an explainer which edges drive the prediction and flag graphs where a small, dominant edge set does all the work. They break on sparse graphs such as molecules: every edge there is critical to the benign prediction, so the explainer cannot tell a benign ring from a planted trigger (Defending Against Backdoor Attack on Graph Nerual Network by Explainability). We propose to fix this with a tool from structural graph theory, the discharging method. Discharging assigns each part of a graph a numerical "charge" whose total is fixed. It then moves charge between neighbors by local rules, and argues that whatever charge cannot be moved away must sit in a small, specific configuration.

We treat each edge's attribution score (how much it contributes to the prediction) as charge. We learn local transfer rules from the training set so that ordinary sparse structure, such as degree-2 chains and rings, passes its high attribution to neighbors and ends near zero. A trigger is a shortcut the model relies on far more than local structure predicts, so its surplus cannot be redistributed and stays concentrated within a bounded radius. The result is a cheap detector that needs no clean validation set and points to where the trigger sits. Because total charge is conserved, it also carries a guarantee: any surplus above the clean budget must appear in some region no wider than the rules reach.

Core Claim

Discharging, as surveyed in An Introduction to the Discharging Method, turns a global conservation law (Euler's formula fixing total charge at $-12$ for planar graphs) into the statement that some local configuration is unavoidable. The method's main weakness is that designing rules by hand is laborious and brittle. Le showed that the rule design itself can be posed as a linear program, with local configurations entering as linear constraints (A Better Bound on the Largest Induced Forests in Triangle-Free Planar Graph). We take the same machinery out of pure combinatorics.

The conserved quantity becomes attribution mass. Many gradient attribution methods sum to the change in model output, which makes that mass a fixed budget. The rules become transfer weights indexed by local structural types, for example "an edge between a degree-2 and a degree-3 atom inside a 6-cycle." The linear program fits these weights on the training set so that benign elements discharge to near zero.

The claim we will test is narrow. On sparse graph-classification data, the charge left after learned discharging separates triggered graphs from clean ones better than raw explainer scores do. It does so specifically because the rules span more than one hop, and not merely because scores are normalized by local type.

Concretely, let $a(x)$ be the attribution of element $x$ (an edge or vertex) in graph $G$. Let $\tau(x)$ be its structural type, and let $w_{\tau\to\tau'}$ be the fraction of charge an element of type $\tau$ sends to each adjacent element of type $\tau'$. The final charge after one round of rules is

$$c^*(x) = a(x) - \sum_{y \sim x} w_{\tau(x)\to\tau(y)}\,a(x) + \sum_{y \sim x} w_{\tau(y)\to\tau(x)}\,a(y),$$

where $y \sim x$ means $y$ is adjacent to $x$. This leaves $\sum_x c^*(x) = \sum_x a(x)$ unchanged. Stacking $r$ rounds gives rules of radius $r$.

The weights solve a linear program. Over the training graphs $\mathcal{D}$ it minimizes a slack-penalized upper quantile of $c^*$:

$$\min_{w \ge 0,\ \beta,\ s \ge 0}\ \beta + \lambda \sum_{(G,x)} s_{G,x} \quad \text{s.t.}\quad c^*_G(x) \le \beta + s_{G,x}\ \ \forall G \in \mathcal{D},\ x \in G.$$

Here $\beta$ is the clean charge ceiling and the slacks $s$ absorb the small poisoned fraction. The program is linear in $w$ because the attributions are fixed before it is solved. The slack term is what removes the need for a verified clean validation set: poisoned samples, typically a few percent, are simply paid for as violations.

The guarantee is the discharging contradiction argument run in reverse. Suppose a graph's attribution total exceeds $\beta$ times the number of its elements. Then some element must end with charge above $\beta$. Its excess can only have come from elements within radius $r$, so a configuration of radius at most $r$ is certifiably anomalous. This is a localization statement, not a certificate of robustness, and we will present it that way.

Research Program

The first stage builds the pipeline. We compute cheap gradient-based edge attributions on a model trained on possibly poisoned data, with one backward pass per graph. Next we define structural types from degree pairs, cycle membership up to length 8, and face length where a planar embedding exists. Most molecular graphs in AIDS and MUTAG are planar, so the original vertex and face charges ($d(v)-6$ and $2\ell(f)-6$) are available as an extra prior channel. Finally we solve the linear program with an off-the-shelf solver for radii $r = 0, 1, 2, 3$. Radius 0 is pure per-type normalization and serves as the critical ablation.

The second stage is analysis. We check whether the learned weights reproduce the qualitative pattern of hand-built discharging, where low-degree sinks receive charge from high-degree reservoirs (Induced forests in bipartite planar graphs). We also measure the radius of the configurations that end up flagged. As a side question, we ask whether triggers anchored at low-degree vertices are stealthier than those anchored at hubs. Rethinking the Trigger-injecting Position in Graph Backdoor Attack left open whether its feature-space finding, that triggers placed on the least important features succeed best, carries over to structure. Our final-charge maps give a direct way to test that.

The third stage is adversarial. An attacker who knows the rules can try to spread the trigger's effect over a radius larger than $r$ so that no single region carries surplus. We predict a trade-off: spreading dilutes the "only creed" dominance that makes backdoors learnable and reliable. We will measure the trade-off rather than assume it.

Baselines

The naive reference is raw attribution thresholding. We flag a graph when its top-$k$ edge attribution mass exceeds a quantile fitted on the training set, with no redistribution. It uses the same attribution, the same poisoned training set and the same threshold-fitting procedure, so any gain over it comes from discharging.

The explainability-score defense of Defending Against Backdoor Attack on Graph Nerual Network by Explainability scores each graph by fidelity minus infidelity and prunes edges adaptively. Its authors report MUTAG attack success dropping from 77% to 5%. It is the method whose sparse-graph failure motivates us, so it must be beaten exactly where it fails. We give it the clean validation set it needs; our method gets none. Beating it means higher detection accuracy and lower post-defense attack success on the sparsest strata of AIDS and MUTAG, binned by average degree.

The strongest existing method is XGBD (XGBD: Explanation-Guided Graph Backdoor Detection). It trains a helper model with a loss that holds clean samples near a fixed value, then checks whether the isolated explanation subgraph reproduces the low-loss prediction. Its authors report 98% detection accuracy on MUTAG under the BadGraph attack, against 89% for ABL and 44% for ExD. It is the strongest competitor because, like our method, it needs no clean validation set. We run it with its own explainer settings on the same poisoned splits, at the same poisoning rates and with the same tuning budget per dataset. Matching its accuracy within about one point while using one backward pass per graph instead of a SubgraphX search would count as a practical win. Exceeding it on the sparse strata or under the adaptive spread-trigger attack would count as a substantive win.

For node classification on Cora and CiteSeer, RIGBD (Robustness Inspired Graph Backdoor Defense) drops edges at random, flags nodes whose predictions vary sharply, and then unlearns them. It reports attack success near 0% (often 0.01% or lower) against GTA, UGBA and DPGBA. We do not expect to beat that number. We include it to see whether our detector stays useful as a training-time-free check where RIGBD is already strong.

The key ablation is radius-0 rules against radius 1 to 3, all with the same type vocabulary and the same linear program.

Why not just…?

Why not just use a stronger explainer such as SubgraphX? Jiang and Li's sparse-graph failure is about what attribution means on sparse graphs, not about explainer quality. When every edge truly matters to the benign prediction, a better explainer reports that more faithfully. XGBD also reports that explanation cost, around one second per graph even with PGExplainer, becomes the bottleneck at scale. Our experiments run discharging on top of both cheap gradients and SubgraphX attributions to separate the attribution source from the redistribution step.

Why not just normalize each edge's attribution by its structural type? This is the most serious threat. If benign high attribution on sparse graphs is fully explained by the type of each edge alone, then radius-0 rules will match the multi-hop rules and the discharging framing adds only a name. The radius ablation settles this directly. If radius 0 is within noise of radius 2 on the sparse strata and under adaptive attacks, we will report that and present the method as type-normalized attribution with a conservation-based localization bound. That would be a smaller but honest result.

Why not just use a structural anomaly detector on the graph alone, ignoring the model? Natural-subgraph triggers defeat structure-only and feature-similarity checks. EUMC samples triggers from the dataset itself and keeps 93.5% attack success on Cora against the Prune+LD defense (Attack by Yourself: Effective and Unnoticeable Multi-Category Graph Backdoor Attacks with Subgraph Triggers Pool). A trigger made of ordinary structure looks normal to any structural prior. What gives it away is that the model leans on it too heavily, and that is why our charge is model attribution rather than Euler charge alone. We include an Euler-charge-only variant to measure this gap.

Proposed Experiments

Graph classification on AIDS, MUTAG and ENZYMES is the primary setting. We use GCN and GIN models, poisoning rates of 1%, 5% and 10%, and two kinds of trigger: GTA's adaptive triggers (Graph Backdoor), which reach over 91.4% attack success on inductive tasks, and random-subgraph BadGraph-style triggers. We add an EUMC-style variant that transplants natural subgraphs drawn from the training set.

We report detection accuracy, precision and recall for poisoned samples, attack success after removing flagged graphs and retraining, clean accuracy drop, and wall-clock time per graph. Every result is also stratified by average degree. The stratification is the decisive check on the motivating gap. Discharging should open its largest margin over the explainability score and raw attribution in the lowest-degree bin; if the margin is flat across bins, the sparse-graph story is wrong.

The second decisive check is the radius ablation described above. The third is an adaptive attacker. It regularizes the trigger so that its final discharged charge stays below $\beta$ everywhere, using the known rules, and we sweep the regularization strength. We plot attack success against detection rate for our method and for XGBD under the same attacker budget. The method earns its place only if that curve shows the predicted dilution, meaning attack success falls as evasion pressure rises. Node classification on Cora and CiteSeer against RIGBD serves as a transfer check, not as the headline.