Source-linked AI summary
Understanding Structural Vulnerability in Graph Convolutional Networks
Liang Chen, Jintang Li, Qibiao Peng, Yang Liu, Zibin Zheng, Carl Yang
TL;DR
Structural attacks can make GCN predictions incorrect, while the reasons for their success have remained unclear. This paper analyzes aggregation robustness using breakdown point theory and proposes median and trimmed-mean aggregation. Experiments report state-of-the-art robustness without sacrificing accuracy.
Problem
Structural attacks can make GCNs predict incorrectly, and the reasons for their success remain unclear despite existing defenses.
Source: §1 · p. 1Method
The paper uses breakdown point theory to analyze weighted-mean aggregation and proposes median and trimmed-mean aggregation for greater robustness.
Source: §1 · p. 1Results
Takeaways & Limitations
The findings identify aggregation robustness as an important factor in GCN robustness against structural attacks.
Source: §1 · p. 2Future work will study non-targeted attacks and whether models can be robust to both targeted and non-targeted attacks.
Source: §7 · p. 7
Abstract
from arXiv · showhide
Recent studies have shown that Graph Convolutional Networks (GCNs) are vulnerable to adversarial attacks on the graph structure. Although multiple works have been proposed to improve their robustness against such structural adversarial attacks, the reasons for the success of the attacks remain unclear. In this work, we theoretically and empirically demonstrate that structural adversarial examples can be attributed to the non-robust aggregation scheme (i.e., the weighted mean) of GCNs. Specifically, our analysis takes advantage of the breakdown point which can quantitatively measure the robustness of aggregation schemes. The key insight is that weighted mean, as the basic design of GCNs, has a low breakdown point and its output can be dramatically changed by injecting a single edge. We show that adopting the aggregation scheme with a high breakdown point (e.g., median or trimmed mean) could significantly enhance the robustness of GCNs against structural attacks. Extensive experiments on four real-world datasets demonstrate that such a simple but effective method achieves the best robustness performance compared to state-of-the-art models.
1 Introduction
GCNs are vulnerable to structural adversarial attacks, but the reasons for this vulnerability have remained unclear. This work links it to the low breakdown point of weighted-mean aggregation and proposes median and trimmed-mean alternatives.
1 Introduction
- Structural changes to edges or nodes can cause GCNs to predict incorrectly, even when attackers lack full knowledge of model parameters.Such unreliable predictions can create opportunities for attackers and restrict GCN applications.Source: §1 · p. 1
- The reasons structural attacks succeed and GCNs are vulnerable remain unclear despite existing empirical and heuristic defenses.Prior defenses include adversarial training, transfer learning, Gaussian node representations, perturbation recovery, and certifiable robustness.Source: §1 · p. 1
- The paper studies targeted test-time evasion against a trained GCN with fixed parameters, where edge modifications aim to fool a target node.It asks why GCNs are vulnerable to structural attacks.Source: §1 · p. 1
- The weighted mean has a low breakdown point, so small structural perturbations can readily change GCN representations.The paper uses breakdown point theory to characterize aggregation robustness and proposes median or trimmed-mean aggregation as alternatives.Source: §1 · p. 1
- Experiments on four node-classification datasets find that robust aggregation improves attack robustness without sacrificing predictive accuracy.The paper compares these methods with state-of-the-art models.Source: §1 · p. 2
2 Related Work
Prior defenses address robustness through representations, detection, or optimization, while leaving GCN aggregation unchanged in several approaches. This work instead explains structural vulnerability through aggregation robustness and proposes median and trimmed-mean schemes.
2 Related Work
- Existing defenses are grouped as robust representation, robust detection, and robust optimization, with different strategies for handling structural attacks.Representation methods seek stable labels in a robust space; detection methods identify edges or nodes to exclude; optimization methods train models to resist extreme embeddings.Source: §2 · p. 2
- Soft Medoid also uses robust message aggregation, while the proposed approach employs high-breakdown-point aggregation to address message-passing vulnerability.The passage identifies the methods as closely related.Source: §2 · p. 2
- Unlike the cited defenses, this work seeks to explain structural-attack success, focuses on targeted evasion, and proposes median and trimmed-mean aggregation.The paper reports state-of-the-art robustness compared with existing works.Source: §2 · p. 2
3 The Structural Vulnerability of GCNs
GCNs update node representations by aggregating neighboring messages, and the paper examines how single-edge structural changes can affect predictions. Its empirical analysis finds that many nodes can be attacked with one edge change, with injection stronger than deletion.
3.1 Graph Convolutional Networks
- A GCN layer updates node representations by aggregating messages from neighboring nodes, with the graph including each target node among its neighbors.The aggregation function is identified as a core GCN design choice, and its weights are static.Source: §3.1 · p. 2
3.2 Empirical Analysis
- The empirical study trains a two-layer GCN and tests all direct structural perturbations within a one-edge budget across dataset nodes.The considered changes include edge injection, deletion, or both.Source: §3.2 · pp. 2–3
- Most nodes can be successfully attacked by changing one edge, including a Cora node with degree 12 and two-hop purity 1.Figure 1 presents degree and purity for successfully attacked nodes; Table 1 reports the percentage attacked.Source: §3.2 · p. 3, Figure 1 · p. 3, Table 1 · p. 3
- Edge injection attacks more nodes than deletion, while the attack success percentage for injection equals that for using both injection and deletion.The authors conclude that injection has stronger attack power than deletion.Source: §3.2 · p. 3
4 Robustness Analysis
The analysis connects structural attacks to GCNs’ neighborhood aggregation: edge changes alter the embeddings being aggregated, and a non-robust aggregation can make the model vulnerable. Breakdown-point analysis shows why weighted mean is sensitive to perturbations and motivates examining direct and indirect attacks.
4.1 Analytical Framework
- Structural attacks change the embeddings supplied to neighborhood aggregation, so a non-robust aggregation function can make the full GCN non-robust.In the example, one perturbation shifts the output to the red class despite most input nodes being blue.Source: §4.1 · p. 3
- The breakdown point measures the maximum fraction of perturbations an aggregation scheme can tolerate before incurring arbitrarily high error.The analysis reduces element-wise aggregation to one dimension and defines breakdown for injected nodes; the breakdown point cannot exceed 1/2.Source: §4.1 · pp. 3–4
4.2 Understanding Structural Vulnerability of GCNs
- A single infinite-valued perturbation makes the weighted mean’s output unbounded, giving it the smallest breakdown point, 1/(|Nv| + 1).The analysis uses breakdown point to quantify the contamination fraction an aggregation scheme can tolerate before its error becomes arbitrarily high.Source: §4.1 · p. 3, §4.2 · p. 4
- Direct edge additions insert perturbations into the target’s weighted-mean input, allowing a small number of changed edges to alter its output.The analysis reports that one perturbation can change classification for around 80% of nodes in Cora and Citeseer.Source: §4.2 · p. 4
- Indirect attacks can affect a target through cascading failures: perturbed neighbors’ representations change before influencing the target’s result.The number of target-neighbor embeddings stays the same; the account assumes attacks constrain changed edges but not changed-node features.Source: §4.2 · p. 4
5 Building Robust Graph Convolutional Networks
The section proposes median and trimmed-mean aggregation as alternatives to GCNs’ weighted mean. Their handling of extreme values is intended to improve robustness to structural perturbations.
5 Building Robust Graph Convolutional Networks
- Median and trimmed-mean aggregation are less affected by perturbations than weighted mean, while all three strategies learn the right representation from clean data.The section reports that the alternatives achieve state-of-the-art performance in experiments.Source: §5 · p. 4
- Median aggregation has a breakdown point of 1/2, because at least as many clean nodes as perturbed nodes must be perturbed to break it.Otherwise, the perturbed values are discarded.Source: §5 · p. 5
- Trimmed mean discards the lowest and highest α fraction of values, averages the remainder, and has a breakdown point of (⌊αn⌋ + 1)/n.A larger α indicates a more robust aggregation.Source: §5 · p. 5
6 Experiments
The experiments compare trimmed-mean and median aggregation with baselines on four benchmark datasets, finding strong robustness under structural attacks and comparable accuracy on clean data.
6.1 Experimental Settings
- Experiments use Cora-ML, Cora, Citeseer, and Pubmed, with train/validation/test splits of 10%/10%/80% and averages over five runs.All models use two layers and 64 hidden units; TMean uses a trimmed percentage α of 0.45.Source: §6.1 · p. 5
6.2 Experimental Analysis
- On clean datasets, trimmed mean and median have accuracy comparable to GCN, with the best performance on Cora and Cora-ML, respectively.Even on Pubmed, their accuracy only slightly underperforms SimPGCN.Source: §6.2 · p. 5, Table 3 · p. 6
- Median aggregation outperforms all baselines in overall robustness; Table 4 covers direct and indirect attacks, with larger values indicating greater robustness.Source: §6.2 · p. 5, Table 4 · p. 6
- For direct attacks, trimmed mean and median generally outperform baselines; at perturbation budget 1 they do so in all cases, while GCN accuracy quickly drops at budget 2.For indirect attacks, the two methods outperform baselines in most cases.Source: §6.2 · p. 6
7 Conclusion
The conclusion attributes one source of GCN structural vulnerability to non-robust aggregation and reports that trimmed mean and median achieve state-of-the-art robustness without sacrificing accuracy. Extending the study to non-targeted attacks remains future work.
7 Conclusion
- The conclusion identifies non-robust aggregation as one reason for structural vulnerability and reports that injecting a small number of edges can easily change its output.Source: §7 · p. 6
- The study leaves analysis of non-targeted attacks and the possibility of models robust to both targeted and non-targeted attacks for future work.Source: §7 · p. 7