Jointly Attacking Graph Neural Network and its Explanations

1 Introduction

• GNNExplainer may help inspectors locate influential users or edges behind abnormal predictions, enabling potential adversarial components to be excluded from the model.The introduction illustrates both an edge included in an explanation and an attack edge that evades it.Source: §1 · p. 2, Figure 1 · p. 2
• The joint attack is difficult because perturbations that cause a malicious prediction are likely to be detected by GNNExplainer, which seeks components informative about that prediction.The paper notes that joint attacks on GNNs and their explanations had rarely been studied.Source: §1 · p. 2
• GEAttack jointly misleads a GNN’s prediction and GNNExplainer’s inspection, with experiments reporting effectiveness against GNNExplainer and PGExplainer.The framework is designed to exploit vulnerabilities in both the model and its explanations simultaneously.Source: §1 · p. 3

Adversarial Attacks on Graphs

• Graph attack methods manipulate graph structure or node features; examples include Nettack [13], RL-S2V [14], NIPA, IG-Attack, and Metattack [25].The methods described include degree- and feature-co-occurrence-preserving perturbations, reinforcement learning, fake-node injection, integrated gradients, and meta-learning.Source: §2 · p. 3

Explaining GNNs

• GNN explanation methods include GNNExplainer [20], PGExplainer [23], GraphLIME [22], and XGNN [21], but this paper targets both GNNs and their explanations on graph data.The related work distinguishes graph explanation from attacks on interpretation methods for non-graph data [39].Source: §2 · p. 3

GNNEXPLAINER

• GNNExplainer returns a local explanation comprising influential subgraph structure and features, optimized for mutual information with the GNN prediction.The explanation is formed from adjacency and feature masks, with thresholding and top-L edge selection used to produce the subgraph.Source: §3 · p. 4

Inspection Performance

• GNNExplainer’s subgraph can narrow an inspector’s search from many edges to influential components for expert review.The paper gives a credit-card fraud example in which experts inspect a generated subgraph and its influential nodes or features.Source: §3 · p. 5
• Around 95% attack success rate (ASR) and around 0.4 NDCG for low-degree nodes indicate that Nettack attacks can be effective while GNNExplainer ranks adversarial edges detectably.The experiments use CITESEER and CORA; higher F1 and NDCG indicate greater likelihood of detection.Source: Figure 2 · p. 4, §3 · p. 5, Figure 3 · p. 5
• The inspection experiment samples 40 target nodes per degree on CITESEER and CORA, uses Nettack to add edges, and evaluates detection with F1 and NDCG.GNNExplainer weights and ranks edges; higher F1 and NDCG indicate adversarial edges are more likely to be detected.Source: §3 · p. 5
• The study focuses on structural perturbations that add fake edges under a budget; feature modifications are left for future work in this preliminary study.The paper frames the experiment as detecting adversarial edges using GNNExplainer’s objective.Source: §3 · pp. 5–6

Problem Statement

• The joint attack requires changing a target node’s prediction to a specified label while keeping added adversarial edges out of the explainer’s output subgraph.The setup focuses on node classification and perturbations to graph structure.Source: §3 · p. 6

4.1 Graph Attack

• The graph attack relaxes the binary adjacency matrix to continuous values, then uses gradients to identify an edge whose addition is likely to cause a wrong prediction.The selected edge has the largest negative gradient value.Source: §4.1 · p. 6

4.2 GNNEXPLAINER Attack

• Because adversarial edges correlate with the target prediction, GNNExplainer may include them in its explanation, making them noticeable to inspectors.The proposed bypass suppresses mask values for candidate adversarial edges while excluding penalties on existing clean edges.Source: §4.2 · pp. 6–7

4.3 GEAttack

• GEAttack combines a prediction-attack loss with a penalty on GNNExplainer’s adjacency mask to attack the model while bypassing explanation-based detection.The parameter λ balances the two losses.Source: §4.3 · p. 7
• GEAttack’s inner loop mimics GNNExplainer’s mask optimization, while its outer loop differentiates the combined loss with respect to the graph structure.The outer-loop gradient passes through the inner updates and uses higher-order gradients to select an edge.Source: §4.3 · p. 7

Algorithm 1 GEAttack

• Algorithm 1 iterates up to the perturbation budget, updating the mask and adding the edge selected by the outer-loop gradient at each iteration.After selecting an edge, it updates the complement mask so that the newly added edge is no longer treated as absent.Source: Algorithm 1 GEAttack · p. 8

5.1 Experimental Settings

• Experiments use CITESEER, CORA, and ACM, compare five attack baselines plus FGA-T&E, and evaluate white-box target attacks using added fake edges.The setup selects 40 victim nodes, sets each node’s perturbation budget to its degree, and averages five runs with standard deviations.Source: §5.1 · p. 8

5.2 Attack Performance Comparison

• GEAttack achieves around 100% attack success across CITESEER, CORA, and ACM, comparable to FGA-T and Nettack and stronger than IG-Attack and random attack.The reported success rates cover attacks with and without target labels.Source: §5.2 · p. 9, Table 1 · p. 9
• Except for random attack, GEAttack is harder for GNNExplainer to detect than the compared methods, with lower Precision, Recall, F1, and NDCG than Nettack and FGA-T.FGA-T&E, which selects edges not chosen by GNNExplainer, still leaves adversarial perturbations detectable.Source: §5.2 · p. 9, Table 1 · p. 9

5.3 Jointly attacking GNNs and PGExplainer

• On CITESEER, GEAttack has the highest ASR/ASR-T against the GNN and outperforms other methods on PGExplainer detection metrics, except random attack.The PGExplainer comparison reports Precision, Recall, F1, and NDCG; similar observations are stated for CORA and ACM but not shown.Source: §5.3 · p. 10, Table 2 · p. 10

5.4 Balancing the Graph Attack and GNNEXPLAINER Attack - λ

• On CORA, GEAttack maintains 100% ASR-T at λ=20, while ASR-T falls to 95% at λ=50 as larger λ favors less detectable edges.Detection rates under F1 and NDCG follow the same trend and stabilize when λ exceeds 50.Source: §5.4 · p. 10, Figure 4 · p. 10

6 Conclusion

• The authors conclude that experiments on several real-world datasets suggest GEAttack is superior to competitive baselines for jointly attacking GNNs and their explanations.They also report model analysis to better understand GEAttack’s behavior.Source: §6 · p. 11
• The paper’s preliminary studies show GNNExplainer can serve as an inspection tool with potential to detect adversarial graph perturbations.This motivates the joint-attack problem addressed by GEAttack.Source: §6 · p. 11
• Current scope covers adversarial edges detected via GNNExplainer, not feature modifications or fake-node injection, and future work would extend to heterogeneous and dynamic graphs.The authors also propose extending the framework to other perturbation types.Source: §6 · p. 11

Supplementary Material: Jointly Attacking Graph Neural Network and its Explanations

• The supplement provides parameter settings, evaluation metrics, dataset details, PGExplainer results in Figure 7, and studies of λ, T, and L in Figures 5, 6, and 8.These materials are presented as support for reproducing the paper’s insights and experimental results.Source: Supplementary Material: Jointly… · p. 14

A Experimental Settings

• For each graph, 10% of nodes are used for training, 10% for validation, and 80% for testing; hyperparameters are tuned on validation loss and accuracy.The implementation is based on DeepRobust, and default settings are used unless stated otherwise.Source: §A.1 · p. 14

• Attack Success Rate (ASR) and ASR-T measure the proportion of target nodes misclassified to any wrong label and to a specified incorrect target label, respectively.Source: §A.2 · p. 14
• Precision@K, Recall@K, and F1@K measure how many adversarial edges appear in the Top-K explanation subgraph, while NDCG@K accounts for their ranked positions.Source: §A.2 · p. 14
• With K set to 15, higher detection metrics indicate adversarial edges are more noticeable, while lower values indicate they are less likely to appear in the subgraph.Source: §A.2 · p. 14

A.3 Datasets

• Experiments use CITESEER, CORA, and ACM node-classification benchmarks, with each graph restricted to its largest connected component.Source: §A.3 · p. 14
• CITESEER and CORA are paper-citation networks with bag-of-words node attributes; CORA has seven classes, while ACM links papers sharing an author and has three classes.Source: §A.3 · p. 15

A.4 Additional Details on Baselines

• The baselines include random edge insertion, gradient-based FGA and targeted FGA-T, Nettack, and integrated-gradients IG-Attack.Source: §A.4 · p. 15
• FGA-T&E adapts targeted FGA-T to evade GNNExplainer by excluding potential nodes in its generated subgraph when selecting adversarial-edge endpoints.Source: §A.4 · p. 15

• Figure 5 examines how subgraph size L affects Precision, Recall, F1, and NDCG detection rates on CORA.Source: Figure 5 · p. 15
• Figure 6 examines how update count T affects F1 and NDCG detection rates on CORA and ACM.Source: Figure 6 · p. 16

B.1.1 Effect of Subgraph Size L

• Detection performance rises as subgraph size L increases, but does not continue improving once L exceeds about 20.Source: §B.1.1 · p. 16

B.1.2 Effect of the Number of Update Iterations T

• GEAttack performs well with fewer than three update steps T, suggesting sub-optimal GNNExplainer solutions provide sufficient gradient signal to guide adversarial-edge selection.Source: §B.1.2 · p. 16