Towards an Efficient General Robust Training Framework for GNNs
Towards an Efficient and General Framework of Robust Training for Graph Neural Networks
The authors propose a GNN robust training framework based on greedy search and zeroth-order methods; on Cora, the GTA attack takes 37 seconds, less than CE-PGD's 147 seconds (Table 3).
At test time, the attacker performs topology perturbations on the graph structure (adding/removing edges), with the number of perturbed edges capped at M, and the adjacency matrix kept symmetric with 0/1 entries; during the attack phase, test-node predicted labels generated by an independently pretrained model may be used. The defender is a GCN node classification model, and robust training has two settings: known model parameters and gradients (GTA), and gradients unavailable (ZO-GTA, gradient-free).
- GNNs are easily misled by adversarial perturbations on the graph structure, while existing robust training methods based on convex relaxation have high computational overhead, are difficult to apply to large graphs, and rely on gradient information, failing when model parameters are unavailable.
- The authors propose the greedy topology attack GTA and its zeroth-order version ZO-GTA to generate discrete structural perturbations, and embed them in the inner maximization of min-max adversarial training, forming a general robust training framework with a replaceable attack module.
- On Cora, Citeseer, and Pubmed, the misclassification rates of GTA/ZO-GTA are close to CE-PGD and CW-PGD, with lower runtime (37 seconds vs. 147 seconds on Cora); GTA-based robust training on Cora has robustness close to CE-PGD training.
- The paper does not specifically discuss limitations. Experiments cover only GCN and three citation network datasets, defense evaluation is only on Cora, attacks consider only topology perturbations, and CE-PGD and CW-PGD are infeasible on Pubmed.
- Evaluated models
- Graph Convolutional Network (GCN)
- Benchmarks
- CoraCiteseerPubmed
- Metrics
- misclassification raterunning time
A general robust training framework for GNNs combines greedy search with zeroth-order methods to defend against graph structure or node attribute perturbations, significantly reducing computational overhead in multiple applications, with robustness superior to current best-performing methods in some scenarios. Existing robust GNN methods are mostly limited to white-box settings with known model parameters, gradient dependence and convex relaxation, making it difficult to scale to time-sensitive tasks and large-scale graph data; this framework addresses these limitations and can cover large-scale problems that traditional robust training struggles to handle.
Paper analysis
What problem does this paper attempt to solve?
The authors state that existing GNN robust training is computationally expensive and gradient-dependent, and propose a general framework based on greedy and zeroth-order methods.
Core question: how to perform adversarial robust training on GNNs on large-scale graph data, even when gradients are unavailable.
- Problem setting: GNNs have been used for tasks such as node classification, but the authors state that carefully designed perturbations of graph structure or node attributes can cause their predictions to be wrong, raising security concerns in high-regret applications.
- Shortcomings of existing methods: The authors state that existing robust training methods (e.g., [12, 13]) rely on convex relaxation over the discrete graph domain, introduce extra computation, and are infeasible on large graphs; moreover, they apply only to white-box settings with known model parameters.
- Core observation: The performance of adversarial training depends on the quality of adversarial examples and the efficiency of the attack algorithm; the discrete constraint prevents gradient descent from being directly used for the inner maximization, and the authors handle the discrete constraint with greedy search and zeroth-order methods.
- Proposed in the paper: two attack methods, GTA (Greedy Topology Attack) and ZO-GTA (Zeroth-order GTA), and a general robust training framework (Algorithm 3) in which the attack module can be replaced.
- Threat model:
- Attacker goal: cause the GCN to misclassify test nodes by perturbing the graph structure (adding or deleting edges).
- Knowledge and capability: the number of perturbed edges is capped at M, and the adjacency matrix remains symmetric with entries 0/1; during attack, predicted labels of test nodes generated by an independently pretrained model may be used (not the true labels).
- Gradient availability: GTA corresponds to the white-box setting where gradients are available; ZO-GTA targets the gradient-free setting where gradients are unavailable (model parameters inaccessible or the model itself discrete).
- Victim system: a GCN performing node classification on Cora, Citeseer, and Pubmed.
What related research exists?
Related work is divided into two categories, GNN attacks and defenses; this paper uses CE-PGD/CW-PGD from [13] as the main comparison baselines.
Adversarial attacks on GNNs
- Dai et al. [14] (2018) — study non-targeted attacks at test time, attacking graph classification and node classification by adding or deleting edges.
- Zügner et al. [15] (2018) — consider both test-time (evasion) and training-time (data poisoning) attacks, allow modification of node attributes, and target a single node; the paper notes that their difference from [14] is that they allow modification of node attributes.
- Zügner and Günnemann [16] (2019) — training-time attack, solving a min-max problem with meta-gradients and optimizing the graph topology as hyperparameters.
Defenses on GNNs
- Xu et al. [13] (IJCAI 2019) — propose GNN adversarial training; the paper notes that this method requires convex relaxation, probabilistic sampling, and binary search, incurs large extra computational overhead, and is infeasible for large graph datasets.
- Zügner and Günnemann [12] (KDD 2019) — study certifiable robustness, obtaining a robust model within a pre-specified bound; the paper notes that this differs from the adversarial training line.
Baselines and benchmarks
- Baseline attack methods: DICE [20], CE-PGD and CW-PGD [13]; the attack experiments follow the hyperparameters and experimental settings of [13].
- Baseline defense method: the CE-PGD adversarial training of [13], compared on Cora.
- Benchmarks: three node classification datasets, Cora, Citeseer, and Pubmed [18].
The authors position this paper as: replacing the convex relaxation line with greedy search and zeroth-order methods, so that robust training remains feasible on large graphs and in scenarios where gradients are unavailable, and they call this a general framework.
How does the paper address this problem?
Generate discrete topology attacks using greedy search (GTA) or zeroth-order greedy (ZO-GTA), embedded in the inner loop of min-max adversarial training.
Overall approach: formulate graph adversarial training as a min-max problem, with the inner layer using a greedy attack that can handle discrete constraints to approximately maximize the loss, and the outer layer using gradient descent to update model weights; the framework is named GTA/ZO-GTA + Robust Training (Algorithm 3).
Problem Formulation
- Adopt the adversarial training form of [17]: minW maxA′ ∈ C L(A′, W; X, yL), where L is the cross-entropy loss on training nodes and A' is the perturbed adjacency matrix.
- The constraint C includes: perturb at most M edges, A' symmetric, A' ∈ {0,1}^(N×N); the discrete constraint prevents gradient descent from being directly used for the inner maximization.
Greedy Topology Attack (GTA, Algorithm 1)
- Fix node attributes X and perturb only edges; the attack objective is to maximize the training loss, i.e., minimize −L(A'; W, X, y_L).
- Each round computes the gradient of the loss with respect to A', multiplies it element-wise with the flipped adjacency matrix to obtain candidates for edge addition/removal and their gradient values; at most n edges with the largest gradients are modified simultaneously, which the authors say speeds up the attack by about n times.
- Only the upper triangle is perturbed and mirrored to the lower triangle to maintain symmetry, so the loop condition is that the perturbation amount is less than 2M; modified edges are recorded in set R to avoid repeated modification.
Zeroth-order GTA (ZO-GTA, Algorithm 2)
- For scenarios where gradients are unavailable or g_A' is too dense, making GTA infeasible on very large graphs, no gradients are computed.
- Each round randomly selects n elements to flip; if the training loss increases, they are kept, otherwise they are flipped back; the discreteness of A' is maintained.
Robust Training Procedure (Algorithm 3)
- T rounds in total: the inner layer fixes W and uses GTA (or ZO-GTA, CE-PGD) to solve the maximization and obtain A'; the outer layer fixes A' and performs one step of gradient descent with learning rate β to update W.
- The authors say the framework is general, and the inner layer can be replaced by any attack method satisfying the constraints; different attacks yield models with different degrees of robustness.
- Parameters used in experiments: T = 1000, β = 0.01, M = 0.05N, n = 0.05N.
What experiments did the paper conduct?
Attack misclassification rate and runtime are measured on three citation networks, and GTA and CE-PGD robust training are compared on Cora.
Experimental Setup
- Model under test: GCN [2], for node classification.
- Datasets: Cora (2,708 nodes, 5,429 edges, 7 classes), Citeseer (3,327 nodes, 4,732 edges, 6 classes), Pubmed (19,717 nodes, 44,338 edges, 3 classes) (Table 1).
- Baseline attacks: DICE, CE-PGD, CW-PGD, following the hyperparameters and settings of [13].
- Metrics: misclassification rate (1 − prediction accuracy on test nodes) and runtime (seconds).
- Protocol: repeated 5 times with different training/test splits, reporting mean ± std; attacks use test-node predicted labels generated by an independently pretrained model (following [16, 13]).
- Parameters: M = 0.05N; n searched in [0.01N, 0.2N] and set to n = 0.05N; robust training T = 1000, β = 0.01.
Main Results
Attack performance (misclassification rate %, according to Table 2) and runtime (seconds, according to Table 3):
Swipe horizontally to read the table
Method Cora misclassification rate Citeseer misclassification rate Pubmed misclassification rate Cora time Citeseer time Clean 18.2 ± 0.1 28.9 ± 0.3 16.9 ± 0.5 — — GTA 25.8 ± 0.1 35.2 ± 0.1 19.3 ± 0.4 37 ± 1 36 ± 1 ZO-GTA 24.9 ± 0.3 33.1 ± 0.3 18.8 ± 0.5 19 ± 3 21 ± 3 DICE 18.9 ± 0.3 29.8 ± 0.4 17.4 ± 0.6 not reported not reported CE-PGD 28.0 ± 0.1 36.0 ± 0.2 infeasible 147 ± 4 144 ± 4 CW-PGD 27.8 ± 0.4 37.1 ± 0.5 infeasible 151 ± 5 142 ± 2 - The authors say GTA/ZO-GTA are competitive with the gradient methods CE-PGD and CW-PGD, with slightly lower misclassification rates but higher computational efficiency.
- On Pubmed, GTA takes 109 ± 5 seconds and ZO-GTA 43 ± 5 seconds; CE-PGD and CW-PGD are infeasible on this dataset (Table 3).
- ZO-GTA has a lower misclassification rate than GTA; the authors attribute this to ZO-GTA being a gradient-free approximation scheme.
Defense Performance (Table 4)
- What was measured: on Cora, GTA robust training and CE-PGD robust training are compared, each evaluated with GTA and CE-PGD attacks.
- Results: the GTA-trained model gives 18.1 ± 0.2% under clean, 20.4 ± 0.3% under GTA attack, and 22.7 ± 3% under CE-PGD attack; the CE-PGD-trained model gives 18.0 ± 0.3%, 20.8 ± 0.4%, and 22.0 ± 0.2%, respectively.
- Authors' interpretation: the two have comparable robustness, but GTA training has lower computational cost, making it suitable for time-sensitive tasks and large graphs.
Effect of Hyperparameter n (Figure 1)
- What was measured: with M = 0.05N fixed, n is varied from 0.01N to 0.2N, observing the misclassification rates of GTA/ZO-GTA on Cora and Citeseer.
- Results: the authors say the misclassification rate decreases as n increases, and GTA is overall higher than ZO-GTA; smaller n requires more attack iterations. Subsequent experiments use n = 0.05N.
Other Ablations and Analysis
- Greedy step size n: Figure 1, n ∈ [0.01N, 0.2N], misclassification rate decreases as n increases (per the authors).
- Choice of inner attack: the defense experiments use GTA rather than ZO-GTA for the inner maximization, because GTA has a higher misclassification rate (Section 4.3).
- Exception: under CE-PGD attack, the standard deviation of the GTA-trained model is ± 3, larger than other settings (Table 4); the paper does not explain this.
What are some points that can be further explored?
The paper does not specifically discuss limitations; experiments cover only GCN and three citation networks, and defense evaluation is only on Cora.
Limitations and future directions noted by the authors
The paper does not specifically discuss limitations and has no Limitations or Future Work section. In the Conclusion, the authors state that the proposed method is a potentially viable candidate for large-scale and time-sensitive problems, and do not list explicit future research directions.
Scope of experiments
- The model under test is only one architecture, GCN (Section 4.1).
- The datasets are three citation networks, Cora, Citeseer, and Pubmed (Table 1); the attack experiments cover all three, while the defense (robust training) evaluation is conducted only on Cora (Section 4.3).
- The attacks consider only topology perturbation (adding or deleting edges), and GTA fixes the node attributes X (Section 3.2.1); the perturbation budget is fixed at M = 0.05N (Sections 4.2 and 4.3).
- The defense evaluation is compared only with the CE-PGD adversarial training of [13], and the evaluated attacks are two, GTA and CE-PGD (Section 4.3).
- Each experiment is repeated 5 times and reports mean ± std (Section 4.1); the paper does not report the total training time of robust training, only the attack generation time (Table 3).
Summarize the main content of the paper
The authors propose the GTA/ZO-GTA attacks and a general GNN robust training framework, claiming it reduces computational cost while maintaining robustness.
A defense paper on adversarial robust training for GNNs, addressing the problems that existing robust training based on convex relaxation is infeasible on large graphs and relies on gradients.
- Method: proposes the greedy topology attack GTA (uses gradients, modifies at most n edges per round) and its zeroth-order version ZO-GTA (random flips, kept or reverted based on loss), embedded in the inner layer of min-max adversarial training; the framework allows replacing with any attack satisfying the discrete constraints (Algorithm 3).
- Attack effectiveness: on Cora, GTA misclassification rate is 25.8 ± 0.1%, CE-PGD is 28.0 ± 0.1%; on Citeseer, they are 35.2 ± 0.1% and 36.0 ± 0.2%, respectively (Table 2).
- Efficiency: on Cora, GTA takes 37 ± 1 seconds, CE-PGD 147 ± 4 seconds; on Pubmed, GTA takes 109 ± 5 seconds, CE-PGD/CW-PGD are infeasible (Table 3).
- Defense effectiveness: on Cora, the GTA robustly trained model has a misclassification rate of 20.4 ± 0.3% under GTA attack and 22.7 ± 3% under CE-PGD attack, close to the CE-PGD-trained model (20.8 ± 0.4%, 22.0 ± 0.2%) (Table 4).
- Authors' conclusion: the authors say the framework has significantly lower computational cost and is more robust in some cases, making GNN robust training possible in large-scale, time-sensitive scenarios.
Related papers
- RGDM: Robust Graph Diffusion ModelDefensesarXiv