# Attacking Graph-based Classification via Manipulating the Graph Structure

arXiv: https://arxiv.org/abs/1903.00553 · HTML: https://mlsanity.com/paper/1903.00553/

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2019.

## Built on by (most cited first, 30 of 53)

- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [Membership Inference Attack on Graph Neural Networks](https://mlsanity.com/paper/2101.06570/) (2021)
- ["Real Attackers Don't Compute Gradients": Bridging the Gap Between Adversarial ML Research and Practice](https://mlsanity.com/paper/2212.14315/) (2022)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learning](https://mlsanity.com/paper/2205.06401/) (2022)
- [Kairos: Practical Intrusion Detection and Investigation using Whole-system Provenance](https://mlsanity.com/paper/2308.05034/) (2023)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [threaTrace: Detecting and Tracing Host-based Threats in Node Level Through Provenance Graph Learning](https://mlsanity.com/paper/2111.04333/) (2021)
- [Transferable Graph Backdoor Attack](https://mlsanity.com/paper/2207.00425/) (2022)
- [Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2211.10782/) (2022)
- [Jointly Attacking Graph Neural Network and its Explanations](https://mlsanity.com/paper/2108.03388/) (2021)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [Instant Graph Neural Networks for Dynamic Graphs](https://mlsanity.com/paper/2206.01379/) (2022)
- [Private Graph Extraction via Feature Explanations](https://mlsanity.com/paper/2206.14724/) (2022)
- [NetFense: Adversarial Defenses against Privacy Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/2106.11865/) (2021)
- [Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks](https://mlsanity.com/paper/2209.05957/) (2022)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees](https://mlsanity.com/paper/2205.03546/) (2022)
- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [Does Black-box Attribute Inference Attacks on Graph Neural Networks Constitute Privacy Risk?](https://mlsanity.com/paper/2306.00578/) (2023)
- [10 Security and Privacy Problems in Large Foundation Models](https://mlsanity.com/paper/2110.15444/) (2021)
- [HGAttack: Transferable Heterogeneous Graph Adversarial Attack](https://mlsanity.com/paper/2401.09945/) (2024)
- [Task and Model Agnostic Adversarial Attack on Graph Neural Networks](https://mlsanity.com/paper/2112.13267/) (2021)
- [On the Security Risks of Knowledge Graph Reasoning](https://mlsanity.com/paper/2305.02383/) (2023)
- [Rethinking Independent Cross-Entropy Loss For Graph-Structured Data](https://mlsanity.com/paper/2405.15564/) (2024)
- [Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attacks](https://mlsanity.com/paper/2110.10482/) (2021)
- [Adversarial Attacks on Fairness of Graph Neural Networks](https://mlsanity.com/paper/2310.13822/) (2023)
- [GUAP: Graph Universal Attack Through Adversarial Patching](https://mlsanity.com/paper/2301.01731/) (2023)
- [Link Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2405.05784/) (2024)

## Abstract (arXiv)

Graph-based classification methods are widely used for security and privacy analytics. Roughly speaking, graph-based classification methods include collective classification and graph neural network. Evading a graph-based classification method enables an attacker to evade detection in security analytics and can be used as a privacy defense against inference attacks. Existing adversarial machine learning studies mainly focused on machine learning for non-graph data. Only a few recent studies touched adversarial graph-based classification methods. However, they focused on graph neural network methods, leaving adversarial collective classification largely unexplored. We aim to bridge this gap in this work. We first propose a threat model to characterize the attack surface of a collective classification method. Specifically, we characterize an attacker's background knowledge along three dimensions: parameters of the method, training dataset, and the complete graph; an attacker's goal is to evade detection via manipulating the graph structure. We formulate our attack as a graph-based optimization problem, solving which produces the edges that an attacker needs to manipulate to achieve its attack goal. Moreover, we propose several approximation techniques to solve the optimization problem. We evaluate our attacks and compare them with a recent attack designed for graph neural networks. Results show that our attacks 1) can effectively evade graph-based classification methods; 2) do not require access to the true parameters, true training dataset, and/or complete graph; and 3) outperform the existing attack for evading collective classification methods and some graph neural network methods. We also apply our attacks to evade Sybil detection using a large-scale Twitter dataset and apply our attacks as a defense against attribute inference attacks using a large-scale Google+ dataset.