Adversarial Attack on Hierarchical Graph Pooling Neural Networks

I. INTRODUCTION

• Most prior GNN attack work addressed node-level tasks, while robustness of graph-classification models had received little study.The introduction identifies hierarchical GNNs as especially relevant to graph classification.Source: §I · pp. 1–2
• The authors identify effective target selection and costly loss-gradient computation as challenges for designing surrogate attacks.The attack framework uses a pooling-score-based loss to avoid computing gradients of the entire network loss for each candidate edge.Source: §I · p. 2
• The paper presents its framework as the first adversarial attack against hierarchical GCN-based graph-classification models.It focuses on HGP models as instances of hierarchical GCNs.Source: §I · p. 2
• The attack uses a convolution-and-pooling surrogate to perturb preserved nodes so the target pooling operator selects the wrong nodes.The method targets nodes selected for preservation and uses a pooling-score-based loss to reduce computation when identifying edge changes.Source: §I · p. 2
• The generated adversarial samples transfer to state-of-the-art graph-classification models, and robustly retrained models defend against the samples.The evaluation covers multiple datasets; the introduction reports both transferability and defense after robust training.Source: §I · p. 2

II. RELATED WORK

• Graph-level attacks were rare; prior graph-classification work used reinforcement learning but was evaluated only on synthetic data, and RL efficiency was a concern.The paper chooses evasion attacks, which generate adversarial samples against a trained model with fixed parameters.Source: §II · pp. 2–3

A. Graph Notation

• The supervised setting represents each attributed graph as G = (A, H), with an adjacency matrix, node-feature matrix, and graph class label.Graphs may have different node counts, and node order is treated as irrelevant to classification and attack.Source: A. Graph Notation · p. 3

B. Hierarchical Graph Pooling (HGP) Model

• HGP models combine convolution and pooling: pooling preserves a subset of nodes and aggregates discarded-node information into them.This hierarchical aggregation is presented as a way to capture graph structure beyond flat propagation through nodes and edges.Source: B. Hierarchical Graph Pooling (HGP)… · p. 3
• The model's convolution follows the previous GCN formulation, using the adjacency and degree matrices at each pooling level and trainable layer weights.The adjacency changes across layers because pooling discards nodes.Source: B. Hierarchical Graph Pooling (HGP)… · p. 3
• Pooling ranks nodes with a score function and preserves high-scoring nodes; the model's final linear layers produce class probabilities.The paper uses a unified pooling operator P to express a pooling layer.Source: B. Hierarchical Graph Pooling (HGP)… · p. 3

C. Adversarial Attacks on Graph

• The evasion attack alternates a lower-level model-training objective with an upper-level adversarial objective evaluated using the trained parameters.The model loss is minimized during training; after training, the fixed model's attack loss is maximized over perturbed graphs.Source: C. Adversarial Attacks on Graph · p. 3
• The adversarial graph is constrained by perturbation restrictions relative to the original graph.The restriction is denoted δ(·).Source: C. Adversarial Attacks on Graph · p. 3

IV. METHODOLOGY

• Nonlinear pooling makes gradients of the attack loss with respect to graph inputs difficult to compute, motivating a new solution.Existing attack losses based on or equal to the model loss make the upper-level attack objective difficult to optimize.Source: §IV · pp. 3–4

A. Workflow of Adversarial Attack

• Figure 1 distinguishes adversarial-sample generation, workflow, and neural-network propagation with red, green, and black arrows, respectively.Source: Figure 1 · p. 4
• The workflow trains a surrogate on original data, generates adversarial test samples, tests them on the surrogate and target HGP models, then retrains target models with adversarial training samples.The target-model attack tests transferability; the paper says robust training is used to improve target-model robustness.Source: A. Workflow of Adversarial Attack · p. 4

B. Surrogate Model

• Because many existing pooling layers are not trainable, the authors use a parameterized self-attention-inspired pooling surrogate to facilitate gradient computation.The surrogate has one convolution layer, one pooling layer, and two fully connected output layers.Source: B. Surrogate Model · p. 4
• In the surrogate, convolution encodes node features before pooling scores nodes, preserves the top K, and sends pooled features to linear layers for graph classification.The node score function is parameterized, and the select function discards unselected nodes.Source: B. Surrogate Model · p. 4

C. Generating Adversarial Samples

• The authors design a new attack loss to avoid computing gradients through the complicated nonlinear model loss.They describe directly using Lmodel as tedious for gradient-ascent optimization of the upper-level objective.Source: C. Generating Adversarial Samples · pp. 4–5
• The attack loss targets preserved nodes by seeking to lower their scores below those of discarded nodes, so pooling selects different nodes and captures different hierarchical information.The paper links this wrong-node selection to wrong prediction outputs.Source: 1) Attack Loss Design · p. 5
• Graph-edge changes are restricted by edit-distance and second-order DELTACON0 budgets, while node-feature changes are restricted by an l1-norm budget.The budgets are denoted △1, △2, and △3, respectively.Source: 2) Unnoticeable Perturbation Restriction · p. 5
• After training the surrogate and fixing its parameters, the attack computes loss gradients for the selected top K nodes and perturbs their features and edges.For each selected node, edge gradients are computed across possible neighbors; the largest absolute edge gradient determines an add or delete operation, while the node feature is updated using its gradient.Source: 3) Gradient-Based Pooling Attack… · p. 5
• The edge-update procedure skips an add or delete when the edge already has the requested state, moving to the next-largest gradient until a valid change is found or the perturbation restriction is reached.Source: 3) Gradient-Based Pooling Attack… · p. 5

D. Computation of Attack Gradient

• For a selected node, the computation considers the attack-loss gradient with respect to its feature vector and each adjacency entry in its row.The section defines the selected node as the attack target and identifies the node feature vector as the corresponding row of H.Source: D. Computation of Attack Gradient · pp. 5–6
• For the feature-gradient derivation, the original-graph score term is constant, leaving only the second term to differentiate.Source: D. Computation of Attack Gradient · p. 6
• The section introduces an assist degree matrix and its elementwise square as part of its matrix definitions.Source: D. Computation of Attack Gradient · p. 6
• For the adjacency-gradient derivation, only the second term, −S(A,H)i, depends on the gradient computation.Source: D. Computation of Attack Gradient · p. 6

• The experiments are organized around dataset descriptions and adversarial-sample generation and surrogate-model attacks.Source: §V · p. 6
• Transferability and attack-power analysis examine the generated adversarial samples.Source: §V · p. 6
• The final parts compare feature and edge attacks and examine model robustness and defense.Source: §V · p. 6

• Six datasets from the Benchmark Data Sets for Graph Kernels cover protein structures, chemical molecular structures, chemical bonds, and biological compounds.Source: A. Dataset · p. 6
• DD graphs represent protein crystal structures, with labels indicating whether the protein is an enzyme.Source: A. Dataset · p. 6
• Table I summarizes the dataset statistics.Source: Table I · p. 7

• In the inductive setting, each dataset is split into 80% training, 10% validation, and 10% testing data.Source: B. Surrogate Model Attack · p. 7
• Adversarial test samples are generated from a fixed trained model under perturbation restrictions intended to keep similarity above 80%.The setting uses Δ1 = 0.05, Δ2 = 0.25, ε = 0.0001, and K = 50%.Source: B. Surrogate Model Attack · p. 7
• Classification accuracy fell by 35.49% on DD, 33.86% on Mutagenicity, 9.46% on ER MD, 10.91% on DHFR, 27.69% on AIDS, and 9.10% on BZR after attack.The comparison is with original training results and uses 5% node perturbation.Source: B. Surrogate Model Attack · p. 7, Table II · p. 7

C. Transferability of the Adversarial Samples

• Adversarial samples generated by the surrogate transfer to HGP-SL and SAG, with the paper attributing this to perturbations of nodes supporting graph hierarchy.The samples can encode different latent hierarchical structure despite looking similar to the originals.Source: 2) Transferability of Adversarial… · p. 7, Table III · p. 7

D. Attack Power Analysis

• The attack-strength analysis limits perturbations to 25% of edges, except for ER MD and DD, where all selected top-K nodes are attacked.The processes are conducted under the unnoticeable restriction.Source: D. Attack Power Analysis · p. 7
• Attack power rises rapidly near 5% edge perturbation, then changes little as additional edges are perturbed.The authors attribute the pattern to early perturbation of important edges that hold hierarchical structure; Figure 2 plots edge perturbation percentage against classification accuracy for SAG and HGP-SL.Source: D. Attack Power Analysis · p. 7, Figure 2 · p. 8

E. Feature Attack v.s. Edge Attack

• The feature-versus-edge experiment uses AIDS and BZR, which include specific node features, and applies a feature-perturbation restriction of Δ3 = 0.05.The authors first attack features with original edges, then combine feature and edge attacks.Source: 1) Experiment Setting · p. 8
• On AIDS and BZR, edge attacks are more powerful than node-feature attacks, while combined attacks are most powerful across datasets and target models.Figure 3 compares node-feature, edge, and combined attacks; its axes are edge perturbation percentage and classification error rate.Source: 2) Feature Attack v.s. Edges Attack · p. 8, Figure 3 · p. 8

F. Robust Train

• Robust-trained models improved performance on adversarial samples with little performance cost on mixed samples.Training mixed original and adversarial data was evaluated on adversarial test data.Source: 2) Robust Train Analysis · p. 9

VI. EVALUATION

• The evaluation compares original and adversarial node-degree distributions using mean KL divergence, where lower values indicate smaller differences.The attack is evaluated in terms of perturbation and its effect on graph hierarchy.Source: §VI · p. 9
• All p-values for GRC and community-louvain comparisons were below 0.05, indicating significant hierarchical-structure differences between original and adversarial samples.Figure 5 illustrates node-degree distributions and hierarchical structure for an example DD graph.Source: §VI · p. 9, Figure 5 · p. 9

VII. CONCLUSION

• The study evaluates only one type of GCN-based method, leaving other graph-classification approaches such as graph kernels and topology methods unverified.The authors identify broader attack strategies for other graph-classification models as future work.Source: §VII · p. 9
• The authors identify the lack of a uniform criterion for measuring unnoticeable graph perturbations and discrete optimization for sample generation as future-work challenges.They call for a more convincing perturbation criterion and a better algorithm for the discrete optimization problem.Source: §VII · p. 10