PaperlayerView exact revision on arXiv

Source-linked AI summary

Attacking Graph-based Classification via Manipulating the Graph Structure

Binghui Wang, Neil Zhenqiang Gong

arXiv:1903.00553v2cs.CR

TL;DR

Adversarial attacks on graph neural networks have been studied, but attacks on collective classification remain largely unexplored. This paper models graph-structure manipulation as an optimization problem and finds that its attacks misclassify collective-classification targets, work without full attacker knowledge, and outperform Nettack for collective classification and some graph neural networks.

  • Problem

    Despite attacks on graph neural networks, adversarial attacks on collective classification via graph-structure manipulation remain largely unexplored, although such methods are adopted to enhance security.

    Source: §1 · p. 1

  • Method

    The paper models attacker knowledge across parameters, training data, and graph completeness, then formulates edge manipulations as an optimization problem with approximate solution techniques.

    Source: §1 · p. 2, §3.2 · p. 4, §4.1 · p. 5

  • Results

    Across evaluations, attacks misclassified collective-classification targets, worked without full attacker knowledge, and outperformed Nettack on collective-classification and some graph-neural-network methods.

    Source: §1 · p. 2, §7 · p. 13

  • Takeaways & Limitations

    Graph-structure attacks are a robustness concern for collective-classification systems and, in some cases, graph neural networks.

    Source: §1 · p. 2, §7 · p. 13

    The paper focuses on LinLBP; extending attacks to random-walk methods and JWP is harder because their edge weights or propagation depend on graph structure.

    Source: §6 · p. 12

Abstract

from arXiv · show

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 develops graph-structure attacks against collective classification, an adversarial setting it describes as largely unexplored, and evaluates their effectiveness across datasets and methods. It models attackers’ knowledge and edge-modification costs, then approximates a constrained optimization problem to evade detection.

1 INTRODUCTION

  • The paper presents the first systematic study of graph-structure attacks on collective classification, addressing a gap left by prior work focused mainly on non-graph data and graph neural networks.It evaluates transfer to other collective-classification and graph-neural-network methods.Source: §1 · pp. 1–2
  • The authors base their attack on LinLBP because it achieves state-of-the-art performance and assigns equal weights to edges, simplifying the optimization problem.They report that LinLBP-based attacks can transfer to other collective-classification and graph-neural-network methods that use graph structure.Source: §1 · p. 2
  • The threat model targets misclassifying an attacker’s positive nodes as negative by increasing their FNR, while accounting for knowledge of parameters, training data, and the graph, and differing edge-modification costs.The objective is to reach a high FNR, such as FNR=1, at minimal total cost.Source: §1 · p. 2
  • The attack minimizes graph-modification cost subject to FNR=1, and approximates this challenging nonlinear binary optimization through continuous relaxation, a reputation-score surrogate with Lagrangian multipliers, and alternating optimization.The binary decisions represent whether to insert or delete each edge.Source: §1 · p. 2
  • Attacks raised FNR from 0 to above 0.90 in many cases and outperformed Nettack on collective classification and non-GCN graph neural networks, while Nettack did better on GCN.The attacks remained effective with substitute parameters, a substitute training dataset, or access to only a 20% partial graph.Source: §1 · p. 2

2 RELATED WORK

Graph-based classification includes collective classification and graph neural networks, but adversarial graph research remains limited and has mainly targeted GNNs. This work addresses collective classification, complementing existing GNN attacks.

2.1 Graph-based Classification Methods

  • Graph-based classification methods broadly comprise collective classification and graph neural networks.Source: §2.1 · p. 2

2.1.1 Collective Classification.

  • Collective classification assigns prior reputation scores, weights graph edges, and propagates scores to classify unlabeled nodes; methods include RW, LBP [23] [25], LinLBP, and JWP.Source: §2.1.1 · p. 2
  • RW propagates reputation through weighted neighbor averaging; LinLBP addresses LBP’s convergence and scalability limitations, and LBP- and LinLBP-based methods outperform RW-based methods.JWP jointly learns edge weights and propagates scores, and outperforms LinLBP; because edge weights must be relearned after edge changes, this work focuses on LinLBP and tests transfer to RW, LBP, and JWP.Source: §2.1.1 · pp. 2–3

2.1.2 Graph Neural Network.

  • GNNs either learn node vectors and labels jointly through neighbor aggregation [5] [38], or learn embeddings first, as in DeepWalk [50] and LINE, before training a classifier.GCN [38] uses spectral graph convolutions to learn vectors and logistic regression to classify nodes; DeepWalk uses random walks and skip-gram, while LINE preserves first- and second-order proximity.Source: §2.1.2 · p. 3

2.2 Adversarial Graph-based Machine Learning

  • Only a few studies address adversarial graph ML; prior work includes clustering [15], attribute manipulation for associative Markov networks, and edge attacks on GNNs such as Nettack.Nettack constrains degree distributions and optimizes a surrogate GCN loss; this work instead attacks collective classification, complementing GNN attacks.Source: §2.2 · p. 3

3 BACKGROUND AND PROBLEM SETUP

The section defines LinLBP [37]’s reputation-based classification, an attacker’s knowledge and graph-editing capabilities, and the minimum-cost objective of making selected positive nodes evade detection.

3.1 Linearized Loopy Belief Propagation

  • LinLBP [37] computes posterior reputation scores from prior scores and weighted graph structure, iterating until convergence and predicting a node negative when its score is below zero.The method uses prior-score parameter θ and a shared edge weight w; the graph’s weight matrix is represented as the element-wise product of adjacency matrix A and W.Source: §3.1 · pp. 3–4

3.2 Threat Model

  • The threat model varies attacker knowledge of LinLBP parameters, training data, and graph completeness, and permits edge insertions or deletions with application-dependent costs and per-node limit K.Attackers know their positive nodes and their interconnections; they may also know a partial subgraph of negative nodes.Source: §3.2 · p. 4

3.3 Problem Definition

  • The attack seeks to manipulate the graph at minimum total cost so LinLBP misclassifies selected target nodes as negative, maximizing their false negative rate.Targets are selected positive nodes and may be only a subset of the positive nodes controlled by the attacker.Source: §3.3 · p. 4, §3.2 · p. 4

4 OUR ATTACKS

The section formulates graph manipulation as a cost-minimizing attack under full knowledge and describes adaptations for attackers with incomplete parameter, training-data, or graph knowledge.

4.1 Adversary with Full Knowledge

  • To make optimization tractable, the method relaxes binary edits to [0, 1], restricts variables to edges touching targets, replaces FNR=1 with negative posterior-score constraints, and alternates edits with score updates.The original problem has O(|V|^2) binary variables and a highly nonlinear FNR constraint.Source: §4.1 · pp. 4–5
  • The full-knowledge attack minimizes edge-modification cost while forcing all target nodes to be classified negative (FNR=1), subject to a per-node edit cap K.Its optimization uses a binary variable for each node pair to represent whether its connection state changes.Source: §4.1 · p. 5

4.2 Adversary with Partial Knowledge

  • For partial-knowledge settings, the attacker substitutes sampled parameters and/or training labels and can run the attack on a known partial graph when those inputs are unavailable.The partial graph may include the attacker’s positive-node subgraph and a collected subgraph of negative nodes.Source: §4.2 · p. 6

5 EVALUATION

The evaluation examines graph-structure attacks on synthetic- and real-positive-node datasets under full and partial attacker knowledge, including their transfer across graph classifiers. It also compares the proposed attack with Nettack at equal modification costs, finding transfer across collective-classification methods and LINE, better Nettack performance against GCN, and much faster execution by the proposed attack.

5.1 Experimental Setup

  • Evaluation covers Facebook (4,039 nodes; 88,234 edges), Enron (33,696 nodes; 180,811 edges), and Epinions (75,877 nodes; 811,478 edges) with synthesized positives, plus Twitter (21M users; 265M edges) with real fraudulent users.Training uses 100 positive and 100 negative nodes for each graph with synthesized positives, and 3,000 of each for Twitter, sampled uniformly at random.Source: §5.1 · pp. 6–7

5.2 Evaluation with Full Knowledge

  • In most full-knowledge scenarios, attacks raised FNR above 0.85 and exceeded the best baseline FNR by 0.2–0.6 across four graphs.The attacks also modified more edges by insertion than deletion; Facebook was the least susceptible graph.Source: Table 2 · p. 8, §5.2 · pp. 8–9
  • Equal cost produced the strongest attacks and Categorical cost the weakest, while CC and CLOSE target selection outperformed RAND.Even under Categorical cost, FNR reached around 0.85 on Enron, Epinions, and Twitter; on Facebook with Equal cost, RAND, CC, and CLOSE yielded FNRs of 0.78, 0.94, and 0.96.Source: Table 2 · p. 8, §5.2 · p. 9
  • Increasing K or the number of attack edges raised FNR, while FNR stayed stable as target-node count grew and total cost increased linearly.FNR increased with attack-edge count partly because collective-classification accuracy already declines as attack edges increase; larger K also raises total cost linearly.Source: Figure 1 · p. 9, §5.2 · pp. 9–10, Figure 2 · p. 9

5.3 Evaluation with Partial Knowledge

  • With partial knowledge, attacks remained effective: FNR was 0.88 with substitute weight 0.5, and knowing 20% of negative nodes yielded FNR close to full-graph knowledge.Attacks were insensitive to substitute θ; increasing substitute training-set size or the known negative-node subgraph improved FNR, while the least-knowledge case showed similar patterns.Source: §5.3 · pp. 10–11

5.4 Transferring to Other Graph-based Classification Methods

  • For Equal cost with CC, attacks achieved ≥0.92 FNR on collective classifiers, versus 0.85 on LINE and 0.54 on GCN.Transferability varied by classifier, was generally stronger for collective classification than graph neural networks, and was lowest for GCN, which the authors speculate is more robust due to higher-order graph convolution.Source: Table 4 · p. 11, §5.4 · p. 12

5.5 Comparing with State-Of-The-Art Attack

  • The authors compare their LinLBP-based attack with Nettack under Equal cost, with Nettack using a degree-distribution-preserving perturbation.The comparison considers FNR and runtime across classifiers on Facebook with CC-selected targets; outcome values are not provided in the supplied passages.Source: §5.5 · p. 12, Table 5 · p. 12
  • The comparison uses Facebook because Nettack is not scalable to the other three graphs; each attack modifies K edge states per target node.Only transferability results to LINE are shown for conciseness.Source: §5.5 · p. 12
  • Against RW, LBP, JWP, and LinLBP, our attack achieves FNRs above 0.90, while Nettack achieves FNRs ≤0.33.The paper attributes this to the attack being designed for LinLBP and transferring well to other collective-classification methods.Source: §5.5 · p. 12
  • For GCN, Nettack achieves a higher FNR than our attack, 0.64 vs. 0.54, while our attack still transfers effectively.Nettack is specifically designed for GCN.Source: §5.5 · p. 12
  • For LINE, our attack achieves an FNR of 0.85 versus Nettack’s 0.58 and is orders of magnitude faster.Source: §5.5 · p. 12

6 DISCUSSION AND LIMITATIONS

The discussion identifies limits in the attack’s scope and outlines future work on other attack targets, defenses, and detection. It also notes that the attacks can alter local graph structure, which may reveal target nodes.

Attacks to other graph-based classification methods

  • RW-based methods and JWP are harder to attack than LinLBP because their graph-dependent edge weights make the adversarial-matrix gradient depend on implicit functions of that matrix.The authors leave specialized attacks for these methods as future work.Source: §6 · p. 12

Unavailability attacks

  • The proposed attacks target increased false-negative rates, but can also slightly increase false-positive rates; specifically increasing FPR to cause unavailability remains future work.A high FPR can cause many negative nodes to be classified as positive, making the system unavailable and eventually abandoned.Source: §6 · p. 12

Poisoning training dataset

  • Training-data poisoning is outside this work’s graph-manipulation focus; future work could study crowdsourced fraud reports that falsely flag normal users and compare methods’ robustness to poisoning.The passage describes dynamically updated, crowdsourced training data as a setting where this attack could arise.Source: §6 · pp. 12–13

Countermeasures

  • Potential defenses include robust-by-design classifiers and detectors for inserted or deleted edges, but detection must account for adaptive attackers who evade both the classifier and detector.One proposed detection approach extracts node-pair features and trains a binary classifier to predict whether a connection state was modified; the defense directions are future work, inspired by defenses against adversarial examples [28] [43] [49] and data poisoning [33].Source: §6 · p. 13

Local-structure detection

  • Attacks slightly decrease target nodes’ average clustering coefficients because they add neighbors that may not be connected, motivating future study of local structures as a way to detect targets or attacks.The comparison is for Equal cost across three social graphs with synthesized positive nodes.Source: §6 · p. 13, Table 7 · p. 13

Attacks to graph-level classification methods

  • The attacks target node-level classification and do not apply to graph-level methods, such as control-flow-graph classification approaches for malware detection; attacks on graph-level classification remain future work.Source: §6 · p. 13

7 CONCLUSION AND FUTURE WORK

The paper presents a systematic study of graph-structure attacks on collective classification, reports their effectiveness and transfer, and outlines directions for extending attacks and improving robustness.

7 CONCLUSION AND FUTURE WORK

  • The study is the first systematic investigation of graph-structure attacks on collective classification, modeling attacker knowledge across parameter, training-dataset, and graph dimensions.It formulates the attack as an optimization problem and proposes techniques to solve it approximately.Source: §7 · p. 13
  • The attacks misclassify target nodes, transfer to graph neural networks, require no access to some true inputs, and outperform existing attacks for collective classification and certain graph neural networks.The evaluation used a large-scale Twitter graph with real positive nodes and three graphs with synthesized positive nodes.Source: §7 · p. 13
  • Future work includes attacks on other graph-based and graph-level classifiers, unavailability and training-data poisoning attacks, and methods to improve classifier robustness.Source: §7 · p. 13

Related papers

Loading 1903.00553v2…