PaperlayerView exact revision on arXiv

Source-linked AI summary

Adversarial Attacks on Graph Neural Networks via Meta Learning

Daniel Zügner, Stephan Günnemann

arXiv:1902.08412v2cs.LGcs.CRstat.ML

TL;DR

The paper asks whether graph neural networks for node classification can be degraded by training-time attacks that perturb discrete graph structure. It uses meta-gradients to solve the resulting bilevel poisoning problem, finding strong performance decreases from small perturbations, including transfer to unsupervised models, without target-classifier access.

  • Problem

    Graph neural networks have improved node classification, but their robustness to training-time attacks on discrete graph structure remains insufficiently understood.

  • Method

    The paper uses meta-gradients for bilevel poisoning attacks, treating the graph as a hyperparameter and using a surrogate when the target classifier is unknown.

  • Results

    Small graph perturbations consistently strongly decrease graph-convolutional classification performance and can transfer to unsupervised embeddings, even reducing performance below a relational-information-free baseline.

  • Takeaways & Limitations

    Training-time graph poisoning can globally compromise node-classification performance under restrictive attack settings and limited knowledge of the target model.

  • Takeaways & Limitations

    The attack is evaluated under constraints including a perturbation budget, preserved connectivity, and limited changes to the graph’s degree distribution, and relies on a surrogate model without target-classifier knowledge.

Abstract

from arXiv · show

Deep learning models for graphs have advanced the state of the art on many tasks. Despite their recent success, little is known about their robustness. We investigate training time attacks on graph neural networks for node classification that perturb the discrete graph structure. Our core principle is to use meta-gradients to solve the bilevel problem underlying training-time attacks, essentially treating the graph as a hyperparameter to optimize. Our experiments show that small graph perturbations consistently lead to a strong decrease in performance for graph convolutional networks, and even transfer to unsupervised embeddings. Remarkably, the perturbations created by our algorithm can misguide the graph neural networks such that they perform worse than a simple baseline that ignores all relational information. Our attacks do not assume any knowledge about or access to the target classifiers.

1 INTRODUCTION

The paper studies robustness of graph convolutional models for semi-supervised node classification, where neighborhood propagation improves predictions but also creates attack vulnerabilities. It proposes a meta-learning poisoning attack that targets global classification performance without access to the target classifier.

  • Node classification infers unlabeled node classes from an attributed network and a subset of labeled nodes.
  • Graph convolutional approaches improve node-classification performance by exploiting information from a node’s neighborhood.
  • Neighborhood propagation also enables indirect adversarial attacks because changing graph structure can alter predictions without changing node attributes.
  • The proposed poisoning algorithm is the first described here to compromise global node-classification performance rather than target one specific node.
  • The approach treats the input graph as a hyperparameter and uses meta-learning to optimize the training process against the model.

2 RELATED WORK

Prior graph attacks were limited in scope, while this work extends meta-learning poisoning to global attacks on deep node-classification models with discrete graph structure. The paper positions its contribution against targeted, test-time, feature-only, and non-deep-learning approaches.

  • Earlier graph adversarial-attack work was sparse and included noise injection for graph clustering without a principled attack-generation procedure.
  • Dai et al. studied test-time attacks on graph and node classification but not poisoning, transferability, or edge insertions, and focused on targeted attacks.
  • Meta-learning traditionally optimizes the learning algorithm itself, including hyperparameters, parameter updates, or activation functions.
  • This paper uses meta-learning oppositely: it modifies training data to worsen performance after training through poisoning attacks.
  • The paper claims the first global poisoning algorithm for deep node-classification models and explicitly formulates the attack as a bilevel optimization problem.

3 PROBLEM FORMULATION

The paper formulates global poisoning of transductive node classification as a constrained bilevel optimization over discrete graph modifications. Because the attacker lacks target-model knowledge and cannot directly optimize unlabeled-node loss, it uses surrogate models and alternative attack losses.

  • 3 PROBLEM FORMULATION: An attributed graph is represented as G = (A, X), with binary adjacency matrix A and node-attribute matrix X.
  • 3 PROBLEM FORMULATION: Node classification maps each node to one of K classes using labeled nodes, while unlabeled nodes and their attributes and edges remain available during transductive training.
  • 3 PROBLEM FORMULATION: The model parameters are learned by minimizing a training loss on labeled nodes, with the whole graph supplied to the model.
  • 3.1 ATTACK MODEL: The attacker seeks to increase the post-training misclassification rate globally, rather than induce an error on one specified node.
  • 3.1 ATTACK MODEL: The attack is constrained by a perturbation budget, connectivity preservation, and a degree-distribution unnoticeability condition.
  • 3.2 OVERALL GOAL: Poisoning is bilevel: the attacker optimizes loss after model parameters have been trained on the modified graph.
  • 3.2 OVERALL GOAL: Because unlabeled test labels are unavailable, one attack loss maximizes labeled-node training loss, Latk = −Ltrain.
  • 3.2 OVERALL GOAL: A second attack loss uses self-learning to estimate unlabeled labels and optimize Lself, while labeled labels remain the only training supervision.

4 GRAPH STRUCTURE POISONING VIA META-LEARNING

The attack treats graph structure as a hyperparameter and uses meta-gradients to optimize poisoning attacks through the model-training process. Because graphs are discrete, the method relaxes gradients for scoring but applies sparse, greedy edge insertions and deletions under attack constraints.

  • 4.1 POISONING VIA META-GRADIENTS: Meta-gradients backpropagate through model training to estimate how perturbing the graph changes the post-training attacker loss.The graph is treated as a hyperparameter, while the training procedure is differentiated to capture training dynamics.
  • 4.1 POISONING VIA META-GRADIENTS: The exact meta-gradient can be computed by unrolling T training steps, but this requires substantial computational and memory resources.The parameters depend on the graph, so derivatives must be chained back through the training trajectory to the initial parameters.
  • 4.1 POISONING VIA META-GRADIENTS: Because graph data are discrete, the method relaxes the data during differentiation but performs discrete updates to preserve sparse adjacency structure.A greedy procedure selects valid edge changes rather than producing dense, continuous adjacency matrices.
  • 4.2 GREEDY POISONING ATTACKS VIA META GRADIENTS: The attack uses a linearized two-layer graph convolutional network as a surrogate while modifying only the graph structure and keeping node attributes constant.The target classifier's parameters, outputs, and architecture are assumed unavailable to the attacker.
  • 4.2 GREEDY POISONING ATTACKS VIA META GRADIENTS: Each possible edge action receives a score from the meta-gradient, with connected pairs sign-flipped to represent edge removal, and the highest-scoring valid perturbation is chosen greedily.The update function inserts absent edges and deletes present edges while enforcing attack constraints.
  • 4.3 APPROXIMATING META-GRADIENTS: First-order and heuristic approximations reduce the cost of exact meta-gradients by avoiding second-order derivatives or the full training trajectory.The experiments compare these approximations with the exact approach and other heuristics; Table 1 reports misclassification rates for 5% perturbed edges.

5 EXPERIMENTS

Experiments evaluate meta-gradient poisoning attacks across graph datasets, models, baselines, perturbation budgets, and attacker-knowledge settings. Small structural changes consistently degrade node-classification performance, can undercut attribute-only baselines, and act primarily by derailing training.

  • Experimental setup: The evaluation covers CITESEER, CORA-ML, and POLBLOGS using GCN, CLN, and logistic regression on DeepWalk embeddings.Datasets are split into 10% labeled and 90% unlabeled nodes; unlabeled labels are used only for evaluation.
  • Heuristics and baselines: All evaluated meta-gradient heuristics increase test misclassification relative to the unperturbed graph, with A-Meta-Both outperforming A-Meta-Self consistently.The study compares self-training and non-self-training variants, including memory-efficient approximations.
  • Heuristics and baselines: 5% edge changes produce the strongest average performance drop across models and datasets, including up to a 48% relative increase in GCN misclassification on CORA-ML.The reported metric is misclassification rate, defined as 1 − accuracy on unlabeled nodes.
  • Heuristics and baselines: Memory-efficient approximations outperform both baselines in many cases and can match the more expensive meta-gradient, while T = 10 surrogate-training iterations significantly reduce effectiveness.The heuristic also succeeds on a dataset with roughly 20K nodes.
  • Transfer and robustness: With only 5% of edges perturbed, GCN and CLN can perform worse than an attribute-only baseline that ignores graph structure.On the clean graph, deep models outperform the baseline; after poisoning, the graph structure instead hurts classification.
  • Transfer and robustness: Changing the graph while holding trained weights fixed has little effect, whereas retraining on the poisoned graph yields low accuracy, indicating that the attack derails training into bad weights.This comparison is reported for a CORA-ML graph with 25% modified edges.
  • Attacker knowledge and perturbation analysis: Roughly 80% of CORA-ML perturbations are edge insertions; inserted edges usually connect different classes, while deleted edges usually connect same-class nodes.These class-based patterns also occur in the DICE baseline and therefore do not by themselves explain the meta-gradient attack’s destructiveness.
  • Attacker knowledge and perturbation analysis: The method remains effective when the attacker optimizes perturbations on a subgraph containing 30% of the original nodes before applying them to the full graph.The limited-knowledge experiment uses the 10% labeled nodes plus randomly selected neighbors.

6 CONCLUSION

The paper proposes meta-gradient poisoning attacks on attributed graphs for node classification, showing that small graph perturbations can strongly degrade graph-model performance and transfer to unsupervised models.

  • Meta-gradients solve the bilevel optimization problem underlying training-time attacks on attributed graphs for node classification.
  • Attacks consistently cause a strong decrease in graph convolutional model classification performance and transfer to unsupervised models.
  • Small perturbations can make graph neural networks perform worse than a baseline that ignores relational information.
  • Approximate meta-gradients are less expensive and often retain a similarly destructive impact on node-classification training.
  • The properties making inserted or removed edges destructive remain an open question relevant to attack detection and defense.

A ALGORITHM

The attack iteratively modifies the graph by differentiating through model training, selecting admissible edge changes under a perturbation budget.

  • The algorithm takes a graph, modification budget, training iterations, and training labels, and outputs a modified graph with unchanged node attributes.
  • It initializes the modified adjacency matrix from the original graph and continues until the number of changed entries reaches the budget.
  • The method computes meta-gradients by backpropagating through the training trajectory.
  • The approximate variant weights training-loss and self-training gradients using λ before selecting an admissible edge modification.
  • At each training iteration, model parameters are updated using gradients of the training loss on labeled nodes.
  • The selected modification maximizes the score among node pairs satisfying graph constraints, with gradient signs flipped for existing edges.

B DATASET STATISTICS

The appendix provides dataset statistics and points to separate PUBMED results in Table 8.

  • Table 6 presents the statistics of the datasets used in the work.
  • Results for PUBMED are reported separately in Table 8 in Appendix F.

C COMPLEXITY ANALYSIS

The attack has quadratic adjacency-related costs, while exact meta-gradients additionally require storing the training trajectory; the unoptimized method is limited to roughly 20K nodes on a commodity GPU.

  • Considering edge insertions and deletions requires gradients for node pairs, giving baseline memory and computational complexity O(N^2).
  • Exact meta-gradient computation additionally requires O(T · |θ|) memory to store the full weight trajectory.
  • Approximate meta-gradient heuristics retain O(N^2) memory complexity because they avoid storing the training trajectory.
  • Without performance optimization, the attacks can run on graphs with roughly 20K nodes using a commodity GPU.
  • Pre-filtering adjacency entries could reduce complexity, but the paper leaves this optimization for future work.

D UNNOTICEABILITY CONSTRAINT

The attacks enforce a degree-distribution unnoticeability constraint that preserves destructive performance while improving attack unnoticeability. The method also extends to binary node-feature attacks combined with graph-structure perturbations.

  • The enforced degree-distribution constraint does not significantly limit the destructive performance of the attacks.
  • The authors conclude that degree-distribution constraints should always be enforced because they improve unnoticeability while attacks remain effective.
  • For binary node features, the same greedy algorithm can attack node features while ignoring degree-distribution constraints.
  • CITESEER is evaluated with simultaneous attacks on node features and graph structure.

F ADDITIONAL RESULTS

Additional experiments evaluate the attack heuristic on PUBMED, different perturbation budgets, shorter surrogate training, and accuracy changes across models and datasets. The reported figures cover CLN, GCN, and Deepwalk on CORA-ML, CITESEER, and POLBLOGS.

  • Additional experiments: The heuristic is evaluated on PUBMED, a dataset with roughly 20K nodes.
  • Additional experiments: Misclassification rates are reported with 1% and 10% perturbed edges.
  • Additional experiments: The surrogate model is also trained for T = 10 iterations to obtain approximate meta-gradients.
  • Additional experiments: Figures 5 through 12 show classification-accuracy changes for CLN, GCN, and Deepwalk across CORA-ML, CITESEER, and POLBLOGS.
  • Additional experiments: The figures separately report CLN, GCN, and Deepwalk accuracy changes for CITESEER and POLBLOGS.
Loading 1902.08412v2…