Attacking Graph-based Classification via Manipulating the Graph Structure

Abstract

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.

To appear in The 26th ACM Conference on Computer and Communications Security, Nov 2019

References in corpus (12)

• Explaining and Harnessing Adversarial Examples
• Adversarial Attacks on Neural Networks for Graph Data
• Delving into Transferable Adversarial Examples and Black-box Attacks
• Poisoning Attacks against Support Vector Machines
• Adversarial Attacks on Graph Neural Networks via Meta Learning
• Is feature selection secure against training data poisoning?
• Poisoning Attacks to Graph-Based Recommender Systems
• Adversarial Attacks on Node Embeddings via Graph Poisoning
• Data Poisoning Attacks on Factorization-Based Collaborative Filtering
• AttriGuard: A Practical Defense Against Attribute Inference Attacks via Adversarial Machine Learning
• Data Poisoning Attack against Unsupervised Node Embedding Methods
• SybilFuse: Combining Local Attributes with Global Structure to Perform Robust Sybil Detection

Cited by in corpus (4)

• Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing
• Influence Function based Data Poisoning Attacks to Top-N Recommender Systems
• Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
• Robust Spammer Detection by Nash Reinforcement Learning