Source-linked AI summary
Attacking Graph-based Classification via Manipulating the Graph Structure
Binghui Wang, Neil Zhenqiang Gong
TL;DR
The paper addresses the limited study of adversarial attacks on collective classification, which is used in graph-based security and privacy analytics. It defines a threat model and an optimization-based graph-manipulation attack with approximation techniques. Across evaluated settings, the attacks evade classification despite incomplete attacker knowledge and outperform existing attacks for collective classification and some graph neural networks.
Problem
Adversarial graph-learning research has mainly focused on graph neural networks, leaving attacks against collective classification largely unexplored.
Method
The paper characterizes attacker knowledge across parameters, training data, and graph access, then formulates edge manipulation as an optimization problem solved approximately.
Results
The attacks effectively evade graph-based classification, work without true parameters, training data, or the complete graph, and outperform existing attacks for collective classification and some graph neural networks.
Takeaways & Limitations
Graph-structure manipulation is a practical attack surface for collective classification and can transfer to other graph-based classification methods.
Takeaways & Limitations
The study focuses on LinLBP because directly optimizing methods whose edge weights depend on graph structure is harder, leaving specialized attacks for those methods as future work.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper studies graph-structure attacks against collective classification, an adversarial setting that existing graph-learning work largely leaves unexplored. It proposes a threat model, optimization-based attacks, approximation techniques, and evaluations across collective-classification and graph-neural-network methods.
- Collective classification is largely unexplored under adversarial graph-structure manipulation, despite extensive adversarial-learning research on non-graph data and recent attacks on graph neural networks.
- The threat model characterizes attacker knowledge of method parameters, the training dataset, and the complete graph, while targeting false negatives among selected positive nodes.
- The attack minimizes graph-modification cost subject to forcing FNR=1 for selected positive nodes, using approximation techniques for nonlinear binary optimization.
- FNR increases from 0 to above 0.90 in many cases, and attacks remain effective with substitute parameters, substitute training data, or only a 20% partial graph.
- The attacks transfer across collective-classification and graph-neural-network methods and substantially outperform Nettack against collective classification.
- The paper systematically studies attacks that manipulate graph edges to evade collective classification.
2 RELATED WORK
Related work distinguishes collective classification from graph neural networks and reviews their graph-based prediction mechanisms. It also shows that adversarial graph learning remains comparatively sparse, with prior attacks concentrated on clustering, associative Markov networks, and graph neural networks.
- Graph-based classification comprises collective classification and graph neural networks.
- Collective classification assigns or learns edge weights, propagates node reputation scores, and classifies unlabeled nodes using posterior scores.
- JWP jointly learns edge weights and propagates reputation scores, making direct attacks difficult because inserted or deleted edges affect weights that must be relearned.
- Some graph neural networks learn node representations and classify nodes simultaneously, whereas graph-embedding methods learn representations first and then train a standard binary classifier.
- Adversarial machine-learning research has mainly addressed non-graph data, while adversarial graph-based machine learning remains much less explored.
- Existing graph attacks target clustering, associative Markov networks, graph neural networks, or complementary graph-based settings rather than collective classification.
3 BACKGROUND AND PROBLEM SETUP
The paper models LinLBP as a graph-based reputation-propagation system and defines attacks that alter edges to make selected positive nodes evade detection. The setup specifies attacker knowledge, manipulation capabilities, costs, node-level limits, and an optimization formulation.
- LinLBP represents graph structure with adjacency matrix A and uniform edge-weight matrix W, producing posterior reputation scores from prior scores.
- LinLBP iteratively computes posterior scores and classifies a node as negative when its converged score is below zero.
- The threat model describes attacker knowledge along Parameter, Training, and Graph dimensions, with graph knowledge either complete or partial.
- The attacker may insert fake edges or delete existing edges, with edge-specific costs and possible per-node limits on the number of modifications.
- The attack targets selected positive nodes and seeks high FNR, ideally misclassifying them as negative at minimal graph-modification cost.
4 OUR ATTACKS
The attack models graph manipulation as a constrained optimization problem targeting selected nodes, then uses approximations to make the problem tractable. The approach alternates posterior-score updates with adversarial-matrix optimization while restricting modifications to target-related edges.
- Attack formulation: The exact optimization is difficult because it has binary variables, O(|V|^2) possible edge decisions, and a highly nonlinear FNR=1 constraint.The formulation includes |V|(|V|−1)/2 binary variables before reduction.
- Attack formulation: The attacker seeks to misclassify selected positive target nodes as negative by finding a minimum-cost adversarial matrix that achieves FNR=1 under per-node edge-modification limits.The matrix contains binary variables for changed connection states, and K bounds inserted or deleted edges per node.
- Approximation techniques: The method relaxes binary variables to [0, 1], binarizes them afterward, and reduces optimization to edges incident to target nodes or connecting target nodes.This reduction avoids modifying edges between negative nodes outside the attacker’s control.
- Approximation techniques: Instead of enforcing FNR=1 directly, the method requires each target’s posterior reputation score to be negative and incorporates this constraint into the objective with a Lagrangian multiplier.A node is predicted negative when its posterior reputation score is negative.
- Alternating optimization: The adversarial graph is represented through the original adjacency matrix, a binarized adversarial matrix, and an edge-weight matrix, whose combination determines the post-attack graph.The matrix |A−B̄| is the adjacency matrix after the attack.
- Alternating optimization: The optimization alternates between updating posterior reputation scores using the current adversarial matrix and updating the adversarial matrix while fixing those scores.Intermediate posterior scores are used rather than waiting for final scores, and projected gradient descent updates the continuous variables.
5 EVALUATION
The evaluation uses three real-world graphs with synthesized positive nodes and a large-scale Twitter graph with real positive nodes. Across cost settings, hyperparameters, partial knowledge, and target methods, the attacks substantially increase FNR and transfer to other graph-based classifiers.
- Experimental setup: The evaluation uses Facebook, Enron, Epinions, and Twitter graphs, with synthesized positives in the first three and real fraudulent users in Twitter.The Twitter graph contains 21M users and 265M edges; Facebook, Enron, and Epinions provide graphs with different properties.
- Full knowledge: Under categorical costs, attacks remain effective, increasing FNR to around 0.85 on Enron, Epinions, and Twitter.Attacks are most effective under Equal cost and least effective under Categorical cost because categorical constraints restrict the search space.
- Full knowledge: Once λ and η exceed graph-dependent thresholds, attacks become effective and FNRs remain stable as the hyperparameters increase.For Facebook, example thresholds are λ=100 and η=0.01; smaller values make attacks less effective or ineffective.
- Partial knowledge: With substitute parameters, attacks achieve Epinions FNRs close to 1 near the true weight of 0.01 and still reach 0.88 with substitute weight 0.5.The attacks are insensitive to θ, while effectiveness generally decreases as the substitute weight moves farther from the true weight.
- Transferability: The attacks remain effective without true parameters, the true training dataset, and/or the complete graph, and transfer to other classifiers.They transfer better to collective classification methods than to graph neural networks in most cases; with Equal cost and CC, FNR reaches at least 0.92 for collective methods, compared with 0.85 for LINE and 0.54 for GCN.
- Comparison with state-of-the-art attack: Against Nettack, the proposed attack exceeds 0.90 FNR on all evaluated collective classifiers, while Nettack reaches at most 0.33; for GCN, Nettack performs better, 0.64 versus 0.54.The proposed attack also reaches 0.85 against LINE versus Nettack’s 0.58 and is orders of magnitude faster.
6 DISCUSSION AND LIMITATIONS
The discussion identifies scope boundaries around the proposed graph-structure attacks, including unsupported attack objectives, training-data poisoning, node-local detection, and graph-level classification.
- Attacks to other graph-based classification methods: The attack design focuses on LinLBP because its uniform edge weights simplify optimization; specialized attacks for RW-based methods and JWP remain future work.RW-based methods and JWP make edge weights or propagation depend on graph structure, complicating optimization.
- Unavailability attacks: The attacks target evasion by increasing false negative rates, while specifically increasing false positive rates remains future work.The paper notes that the attacks may slightly increase FPR but were not designed to optimize it.
- Poisoning training dataset: Training-dataset poisoning is an unaddressed alternative attack surface when labels are dynamically collected or updated.The paper gives crowdsourced fraud reports as an example of how an attacker could poison training data.
- Local-structure detection: Local structural changes may expose attacked positive nodes because the attacks can slightly reduce their clustering coefficients.The paper attributes this decrease to adding neighbors that may not be connected to one another.
- Attacks to graph-level classification methods: The attacks address node-level classification and are not applicable to graph-level classifiers such as control-flow-graph malware detectors.Graph-level methods make predictions for entire graphs rather than individual nodes.
7 CONCLUSION AND FUTURE WORK
The paper presents a systematic framework for attacking collective classification through graph manipulation, combining a threat model with an approximately solvable optimization formulation. Evaluations show effective misclassification, transfer across method families, limited knowledge requirements, and improved performance over existing attacks, while several attack and defense extensions remain future work.
- The study systematically examines attacks on collective classification by manipulating graph structure.
- The threat model characterizes attacker knowledge across the Parameter, Training dataset, and Graph dimensions.
- The attack is formulated as an optimization problem and approximately solved using the proposed techniques.
- Evaluations show that the attacks misclassify target nodes, transfer to graph neural networks, work without true parameters, training data, or the complete graph, and outperform existing attacks for collective classification and certain graph neural networks.
- Future work includes specialized attacks for other graph-based methods, unavailability and poisoning attacks, graph-level attacks, and robustness enhancements.