Graph Structure Learning for Robust Graph Neural Networks

Wei Jin; Yao Ma; Xiaorui Liu; Xianfeng Tang; Suhang Wang; Jiliang Tang

Source-linked AI summary

Graph Structure Learning for Robust Graph Neural Networks

Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, Jiliang Tang

arXiv:2005.10203v3May 20, 2020cs.LGcs.CRcs.SIstat.ML

TL;DR

GNNs are vulnerable to adversarial graph perturbations, motivating defenses that exploit intrinsic properties of clean graphs. Pro-GNN jointly learns a clean graph structure and GNN parameters using sparsity, low rank, and feature smoothness, and experiments report stronger robustness than state-of-the-art defenses under varied attacks.

Problem
GNN performance can greatly degrade under subtle adversarial graph perturbations, while defenses exploiting clean-graph properties remain limited.
Method
Pro-GNN jointly learns a clean graph structure and GNN parameters from a perturbed graph guided by sparsity, low rank, and feature smoothness.
Results
Pro-GNN consistently outperforms state-of-the-art baselines under varied adversarial attacks, including improvements over GCN of 22%, 12%, and 14% at 25% perturbation on three datasets.
Takeaways & Limitations
Learning graph structure together with the GNN improves robustness across different attack types and perturbation rates.
Takeaways & Limitations
JaccardGCN and Pro-GNN cannot be directly applied to datasets without node features.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. However, recent studies show that GNNs are vulnerable to carefully-crafted perturbations, called adversarial attacks. Adversarial attacks can easily fool GNNs in making predictions for downstream tasks. The vulnerability to adversarial attacks has raised increasing concerns for applying GNNs in safety-critical applications. Therefore, developing robust algorithms to defend adversarial attacks is of great significance. A natural idea to defend adversarial attacks is to clean the perturbed graph. It is evident that real-world graphs share some intrinsic properties. For example, many real-world graphs are low-rank and sparse, and the features of two adjacent nodes tend to be similar. In fact, we find that adversarial attacks are likely to violate these graph properties. Therefore, in this paper, we explore these properties to defend adversarial attacks on graphs. In particular, we propose a general framework Pro-GNN, which can jointly learn a structural graph and a robust graph neural network model from the perturbed graph guided by these properties. Extensive experiments on real-world graphs demonstrate that the proposed framework achieves significantly better performance compared with the state-of-the-art defense methods, even when the graph is heavily perturbed. We release the implementation of Pro-GNN to our DeepRobust repository for adversarial attacks and defenses (footnote: https://github.com/DSE-MSU/DeepRobust). The specific experimental settings to reproduce our results can be found in https://github.com/ChandlerBang/Pro-GNN.

1 INTRODUCTION

GNNs achieve strong graph representation learning but can be severely degraded by subtle adversarial perturbations. Pro-GNN exploits graph properties that attacks violate to jointly recover structure and learn a robust model.

GNNs support graph representation learning and downstream tasks including node classification, link prediction, and recommendation.
Adversarial attacks can greatly degrade GNN performance through unnoticeable graph perturbations, creating risks for safety-critical applications.
Clean real-world graphs are often low-rank and sparse, while adjacent nodes tend to have similar features.
Adversarial attacks enlarge adjacency singular values, rapidly increase rank, and connect nodes with large feature differences, violating these graph properties.
Pro-GNN jointly learns a clean graph structure and GNN parameters using sparsity, low rank, and feature smoothness, outperforming state-of-the-art defenses in experiments.

2 RELATED WORK

Prior work develops GNN architectures and defenses against graph adversarial attacks, but existing defenses have important data or attack-specific constraints. Pro-GNN instead recovers graph structure while learning GNN parameters simultaneously.

GNNs: GNNs comprise spectral and spatial methods for learning representations from graph data.
Adversarial attacks: Graph adversarial attacks exploit discrete, interdependent graph structure to produce subtle perturbations that can fool GNNs.
Defense methods: Existing defenses include attention-based models, Gaussian-distribution representations, feature-similarity pruning, and methods requiring additional clean graphs.
Pro-GNN: Pro-GNN differs by recovering intrinsic graph structure from perturbed graphs while simultaneously learning GNN parameters across different attacks.

3 PROBLEM STATEMENT

The paper formulates robust node classification as jointly learning a clean adjacency matrix and GNN parameters from a graph with poisoned structure and partial labels. It introduces the graph, feature, label, and model notation used for this objective.

Notation: A graph is represented as G = (A, X), where A encodes node relations and X contains node feature vectors.
Node classification: Only a subset of nodes has labels, and the GNN must predict labels for the remaining unlabeled nodes.
Node classification: The node-classification objective learns parameters θ by minimizing prediction loss between labeled-node outputs and their true labels.
GCN formulation: The framework focuses on a two-layer GCN but is described as extendable to other GNN models.
Problem definition: Given poisoned adjacency A, unperturbed features X, and partial labels, the problem is to jointly learn clean structure S and parameters θ for unlabeled-node classification.

4 THE PROPOSED FRAMEWORK

Pro-GNN reconstructs a clean graph from poisoned data by enforcing low-rank, sparse, and feature-smooth structure while jointly training a task-specific GNN. Its objective combines graph reconstruction, structural regularization, feature smoothness, and GNN loss, optimized by alternating updates.

Framework overview: Pro-GNN iteratively reconstructs the clean graph by preserving low rank, sparsity, and feature smoothness while updating GNN parameters on the reconstructed graph.The framework addresses graph learning and robust GNN training jointly through an alternating schema.
4.1 Exploring Low rank and Sparsity Properties: Adversarial edges can connect different communities, increase adjacency-matrix rank and singular values, and damage graph sparsity and low-rank structure.Removing adversarial edges decreases rank faster than removing normal edges, motivating structural constraints.
4.1 Exploring Low rank and Sparsity Properties: The learned adjacency matrix stays close to the poisoned matrix while symmetry, sparsity, and low-rank constraints guide reconstruction.The ℓ1 norm promotes sparsity, whereas the nuclear norm promotes low rank and reduces enlarged singular values.
4.2 Exploring Feature Smoothness: Feature smoothness penalizes large feature differences between connected nodes using the normalized graph Laplacian.The normalized Laplacian makes the smoothness measure independent of node degrees, and smaller Ls indicates smoother features.
4.3 Objective Function of Pro-GNN: Pro-GNN jointly learns graph structure and GNN parameters because a graph learned in a separate preprocessing stage may be suboptimal for the downstream task.The final objective includes reconstruction, ℓ1, nuclear-norm, feature-smoothness, and GNN-loss terms; GNN loss also guides graph learning.
4.4 An Optimization Algorithm: The optimization alternates between updating GNN parameters with fixed S and updating S with fixed θ under structural constraints.The θ update is a typical GNN optimization solvable by stochastic gradient descent.

11 Return S,θ

The graph-structure update uses forward-backward and proximal methods to handle non-differentiable sparsity and low-rank regularizers, followed by projection onto the feasible graph set. Training initializes the estimated graph with the poisoned adjacency matrix and alternates graph and GNN updates.

Graph update: Forward-backward splitting alternates a gradient-descent step with a proximal step for updating the learned graph.The proximal operator handles the regularization term R(S).
Graph update: Incremental Proximal Descent cyclically applies proximal updates for the ℓ1 and nuclear norms when both regularizers are non-differentiable.The method uses singular-value decomposition for the nuclear-norm proximal operator.
Projection: After learning a relaxed S, projection enforces symmetry and clips each Sij to the interval [0, 1].The projection averages S with its transpose for symmetry and maps values below 0 or above 1 to the nearest boundary.
Training algorithm: Training initializes S with poisoned adjacency A, randomly initializes θ, and alternates their updates until the stopping condition is met.The GNN parameters are trained every iteration, while the graph reconstruction model is trained every τ iterations.

5 EXPERIMENTS

The experiments evaluate Pro-GNN on four benchmark graphs against representative GNN and defense baselines under adversarial attacks. Results use 10% training nodes, 10% validation nodes, 80% testing nodes, and averages over 10 runs.

Evaluation Questions: The experiments assess Pro-GNN under non-targeted, targeted, and random attacks to compare defense performance across attack types.
Datasets: Pro-GNN is evaluated on Cora, Citeseer, Pubmed, and Polblogs, with identity features used for Polblogs because node features are unavailable.
Baselines: The comparison includes GCN, GAT, RGCN, GCN-Jaccard, and the Pro-GNN-fs variant without the feature smoothness term.
Experimental Protocol: Each graph uses 10% of nodes for training, 10% for validation, and 80% for testing, with average performance reported over 10 runs.

5.2 Defense Performance

Pro-GNN is tested against non-targeted, targeted, and random graph attacks. It consistently outperforms the compared defenses, including under heavy perturbation, while feature smoothness improves performance especially at higher perturbation rates.

Non-targeted Attack: Pro-GNN consistently outperforms other methods across perturbation rates under non-targeted metattack.
Non-targeted Attack: At 25% perturbation, Pro-GNN improves vanilla GCN by 22%, 12%, and 14% on the three reported datasets, respectively.
Ablation: Pro-GNN exceeds Pro-GNN-fs especially at large perturbation rates, supporting feature smoothing as useful for removing adversarial edges.
Targeted Attack: At five perturbations per targeted node on Citeseer, Pro-GNN improves vanilla GCN by 23% and outperforms other defenses by 11%.
Random Attack: Under random noise ratios from 0% to 100%, Pro-GNN consistently outperforms all baselines and successfully resists random attack.
Overall Finding: Across the evaluated settings, Pro-GNN is reported to defend various types of adversarial attacks.

5.3 Importance of Graph Structure Learning

The learned graph assigns substantially smaller weights to adversarial edges and remains useful for classification under heavy poisoning. Pro-GNN outperforms both using no graph structure and the standard GCN in this setting.

Normal Edges Against Adversarial Edges: Adversarial edges receive much smaller weights than normal edges in Pro-GNN’s learned adjacency matrix.This pattern is observed on Pubmed and Polblogs under metattack.
Performance on Heavily Poisoned Graph: At 25% metattack perturbation, removing the graph structure makes GCN-NoGraph outperform GCN.With an all-zero adjacency matrix, GCN reduces to a feature-only feed-forward neural network.
Performance on Heavily Poisoned Graph: Pro-GNN substantially outperforms GCN-NoGraph under heavy poisoning, indicating that it retains useful graph structural information.The comparison is reported in Table 3 for node classification under 25% perturbation.

5.4 Ablation Study

The ablation study shows that Pro-GNN’s regularizers contribute differently to defense performance, while jointly learning graph structure and GNN parameters improves robustness across perturbation levels.

Regularizers: Pro-GNN-α improves over vanilla GCN mainly when perturbations are large, whereas Pro-GNN-β and Pro-GNN-λ perform much better than vanilla GCN.Pro-GNN-β outperforms all variants except the full Pro-GNN model.
Regularizers: Incorporating the different components enables Pro-GNN to explore graph properties and consistently outperform state-of-the-art baselines.The components correspond to sparsity, low rank, GNN loss, and feature smoothness.
Joint Structure and Parameter Learning: The two-stage Pro-GNN-two performs well under large perturbations but fails at relatively low perturbation rates, unlike joint learning.The experiment uses metattack on Cora.

5.5 Parameter Analysis

Pro-GNN is sensitive to its hyper-parameters, especially the sparsity and feature-smoothness weights. Appropriate settings improve accuracy, whereas overly large values can substantially harm performance.

Parameter Sensitivity: Appropriate values of α, β, γ, and λ can boost Pro-GNN’s accuracy on Cora under 10% metattack perturbation.The analysis varies α, β, γ, and λ across specified ranges and reports results in Figure 7.
Parameter Sensitivity: Large α and λ values greatly hurt performance because excessive sparsity or feature smoothness can produce inaccurate graph-structure estimates.The passage contrasts α and λ with γ, for which the reported sensitivity differs.

6 CONCLUSION

Pro-GNN jointly learns graph structure and GNN parameters to defend against graph adversarial attacks. Experiments report consistently stronger robustness than state-of-the-art baselines under varied attacks.

Conclusion: Pro-GNN learns graph structure and GNN parameters simultaneously as a defense against graph adversarial attacks.The framework targets attacks that can rapidly degrade GNN performance.
Conclusion: Experiments show that Pro-GNN consistently outperforms state-of-the-art baselines and improves overall robustness under various adversarial attacks.The conclusion identifies exploration of additional graph properties as future work.