PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Gradient Attack on Network Embedding

Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, Qi Xuan

arXiv:1809.02797v2physics.soc-phcs.SI

TL;DR

Network embedding enables important network-analysis tasks but can expose target nodes to identification, creating privacy and robustness concerns. The paper proposes FGA, which uses iterative GCN gradient information to modify links in adversarial networks. Across multiple embedding methods and real-world networks, FGA outperforms baseline attacks and can disturb embeddings by rewiring few links.

  • Problem

    Network embedding supports tasks such as node classification, link prediction, and community detection, but network-analysis attacks are relevant for protecting user privacy and understanding method robustness.

  • Method

    FGA iteratively selects the node pair with maximum absolute gradient from a GCN-based adversarial network generator and updates the modified links.

  • Results

    FGA achieves higher Attack Success Rates and lower Average number of Modified Links than baseline attacks across considered network embedding methods and real-world networks.

  • Takeaways & Limitations

    FGA can transfer from GCN to other network embedding methods and disturb their embeddings by modifying relatively few links.

  • Takeaways & Limitations

    The authors identify the need for future network embedding methods that are more robust to adversarial attacks generated by FGA.

Abstract

from arXiv · show

Network embedding maps a network into a low-dimensional Euclidean space, and thus facilitate many network analysis tasks, such as node classification, link prediction and community detection etc, by utilizing machine learning methods. In social networks, we may pay special attention to user privacy, and would like to prevent some target nodes from being identified by such network analysis methods in certain cases. Inspired by successful adversarial attack on deep learning models, we propose a framework to generate adversarial networks based on the gradient information in Graph Convolutional Network (GCN). In particular, we extract the gradient of pairwise nodes based on the adversarial network, and select the pair of nodes with maximum absolute gradient to realize the Fast Gradient Attack (FGA) and update the adversarial network. This process is implemented iteratively and terminated until certain condition is satisfied, i.e., the number of modified links reaches certain predefined value. Comprehensive attacks, including unlimited attack, direct attack and indirect attack, are performed on six well-known network embedding methods. The experiments on real-world networks suggest that our proposed FGA behaves better than some baseline methods, i.e., the network embedding can be easily disturbed using FGA by only rewiring few links, achieving state-of-the-art attack performance.

1 INTRODUCTION

Network embedding supports diverse network-analysis tasks, but its use in sensitive settings raises privacy and robustness concerns. The paper introduces FGA to generate adversarial networks and evaluates it across multiple embedding methods, reporting stronger attacks than baselines.

  • Network embedding learns low-dimensional node or link representations for applications including link prediction, node classification, and community detection.
  • Adversarial attacks on network analysis aim to protect user privacy or assess the robustness of network-analysis methods.
  • NETTACK iteratively modifies candidate links or features for GCN node classification but is limited to that task, with little discussion of attack transferability.
  • FGA generates adversarial networks using iterative gradient information from pairwise nodes based on a trained GCN model.
  • FGA attacks GCN and other embedding methods, including GraRep, DeepWalk, node2vec, LINE, and GraphGAN, using multiple attack strategies.
  • FGA achieves higher Attack Success Rates and lower Average number of Modified Links than NETTACK and DICE on real-world networks.

2 METHOD

The method section introduces FGA as a framework that generates adversarial networks with a GCN model.

  • FGA uses a GCN-based adversarial network generator for network embedding attacks.
  • The framework summarizes the symbols used in its formulation in a dedicated table.
  • The method section positions adversarial network generation as the central mechanism of FGA.

2.1 Problem Definition

Network embedding maps network nodes into a lower-dimensional feature space for downstream analysis, while an embedding attack modifies selected links to hide target nodes.

  • Network embedding maps each node v_i to a d-dimensional feature vector y_i, with d much smaller than the number of nodes.
  • A network embedding attack selects key links and constructs a perturbation network with modification indicators M_ij in {-1, 0, 1}.
  • The attacked network is formed from modified links and is intended to make target nodes misclassified with relatively high probability.

2.2 The Framework of FGA

FGA generates adversarial networks from GCN gradients and uses them to hide selected target nodes from network-analysis models, including methods beyond GCN.

  • The framework first trains a GCN on the original network and computes a target loss for each target node.
  • It evaluates gradient information for node pairs and selects the pair with maximum absolute gradient to update the adversarial network.
  • The generated adversarial network is used to protect target nodes from GCN detection and can transfer to other network embedding methods.

2.3 Adversarial Network Generator via GCN

The paper uses a trained GCN to derive link gradients and iteratively construct an adversarial network. At each iteration, it selects the feasible node pair with the largest absolute gradient and modifies that link to increase the target loss.

  • GCN model: The GCN uses the adjacency matrix, node features, and trainable weights to produce node-classification outputs and a cross-entropy loss.The adjacency matrix includes self-connections and is normalized using its degree matrix.
  • Link gradient: The adjacency matrix is treated as a loss-function variable, so its gradients can be used to induce target-node misclassification.The attack maximizes a target loss representing the difference between the target node’s predicted and real labels.
  • Link gradient: A positive or negative link gradient indicates whether adding or deleting a node pair’s link increases target loss, while its magnitude measures classification influence.The gradient matrix is symmetrized because the network is undirected.
  • Adversarial network generator: The generator constructs a link-gradient network from the current adversarial adjacency matrix and selects the feasible node pair with maximum absolute gradient.Pairs whose indicated addition or deletion is impossible are ignored.
  • Adversarial network generator: Each iteration modifies one link using the selected gradient sign, starting from the original network and continuing for K iterations.The output is the adversarial network with adjacency matrix ˆA^K.

2.4 White-Box Adversarial Attack

The white-box attack uses the generated adversarial network against the GCN model, with direct, indirect, and unlimited variants defining which links may be changed.

  • White-box setting: The white-box setting attacks the GCN model with an adversarial network containing tiny perturbations, causing the retrained model to misclassify target nodes.The attack is performed in direct, indirect, and unlimited forms.
  • Direct attack: Direct attack modifies only links around target nodes by removing existing links or adding new ones to them.This setting models an attacker who can manage immediate neighborhoods but has limited knowledge beyond friends.
  • Indirect attack: Indirect attack changes links not immediately connected to target nodes when those links affect target-node classification and may provide greater concealment.The paper motivates indirect modifications as potentially preferable for a network manager seeking a concealed attack.
  • Unlimited attack: Unlimited attack permits adding or removing a link between any node pair to seek the maximum attack effect.Unlike the other variants, it imposes no direct- or indirect-link restriction.

2.5 Black-Box Adversarial Attack

The paper evaluates whether adversarial networks generated with GCN transfer to other network embedding methods and examines attacks on structurally important nodes.

  • Transferability: The GCN-generated adversarial attack is applied to other embedding methods to test whether its effectiveness transfers across methods.The authors motivate this test by noting that embedding methods with downstream classifiers or regressors may have similar decision boundaries.
  • Security concern: The paper identifies transferability as a security concern because adversarial examples may be crafted without knowing the target embedding method beforehand.This consequence follows from the stated cross-method attack setting.
  • Critical nodes: The attack is also performed on hub and bridge nodes because these nodes play important roles in network dynamics and algorithms.This experiment examines the antiattack ability of FGA on critical network components.

3 EXPERIMENTS

Experiments compare FGA with baseline attacks across three datasets, multiple network embedding methods, and attack settings. FGA generally achieves higher attack success with fewer modified links, while performance varies by network structure and target-node type.

  • Experimental setup: Experiments evaluate FGA against RA, DICE, and NETTACK across Pol.Blogs, Cora, and Citeseer network datasets.The evaluation covers GCN and five additional embedding approaches, using ASR and AML to measure attack effectiveness.
  • Evaluation metrics: ASR measures the fraction of target nodes misclassified after changing no more than γ links, while lower AML indicates a stronger attack.The perturbation size γ ranges from 1 to 20 links.
  • Uniform attack: Unlimited FGA outperforms all other attacks in ASR and AML across the considered embedding methods and datasets.For Cora and Citeseer, unlimited FGA reaches 100% ASR after changing 20 links; Pol.Blogs reaches 84.47% ASR on average, partly reflecting its denser structure.
  • Uniform attack: On Cora and Citeseer, unlimited FGA needs no more than 6 changed links on average to attack a target embedding across the considered methods.Direct FGA also generally outperforms NETTACK and DICE, while white-box attacks on GCN require fewer than 4 links on average in these datasets.
  • Uniform attack: Indirect FGA performs reasonably on sparse Cora and Citeseer but is ineffective on denser Pol.Blogs, where it exceeds random attack only.Changing links far from the target can preserve the target’s local structure and make the attack more concealed.
  • Computational cost: FGA’s running time increases linearly with modified links and is substantially lower than NETTACK’s on Cora.NETTACK is slower because it selects candidate links using degree-distribution information at every iteration.
  • Special target nodes: For hub and bridge nodes, unlimited FGA remains strongest, but these nodes are harder to attack than normal nodes and distant-link changes are less effective.Bridge-node embeddings are relatively easier to attack than hub-node embeddings; community-deception results show the same overall ranking as node classification.

4 CONCLUSION

The paper introduces FGA, a GCN-based framework that iteratively selects maximum-gradient node pairs to generate adversarial networks and disturb network embeddings. Its results support strong attack performance, while future work recognizes the need for embedding methods that are more robust to FGA.

  • FGA uses GCN gradients to select node pairs with maximum absolute link gradients and iteratively update an adversarial network.The process stops when the number of modified links reaches a predefined value.
  • Experiments cover uniform, hub-node, and bridge-node attacks on six network embedding methods, with node classification evaluated across three networks.
  • FGA outperforms baseline attack methods across the reported attack settings and achieves state-of-the-art results.
  • Future work will seek network embedding methods that are more robust to adversarial attacks generated by FGA.The paper notes that embedding and attack methods may improve iteratively.
Loading 1809.02797v2…