AN-GCN: An Anonymous Graph Convolutional Network Defense Against Edge-Perturbing Attack

Ao Liu, Beibei Li, Tao Li, Pan Zhou, Rui Wang

Abstract

Recent studies have revealed the vulnerability of graph convolutional networks (GCNs) to edge-perturbing attacks, such as maliciously inserting or deleting graph edges. However, a theoretical proof of such vulnerability remains a big challenge, and effective defense schemes are still open issues. In this paper, we first generalize the formulation of edge-perturbing attacks and strictly prove the vulnerability of GCNs to such attacks in node classification tasks. Following this, an anonymous graph convolutional network, named AN-GCN, is proposed to counter against edge-perturbing attacks. Specifically, we present a node localization theorem to demonstrate how the GCN locates nodes during its training phase. In addition, we design a staggered Gaussian noise based node position generator, and devise a spectral graph convolution based discriminator in detecting the generated node positions. Further, we give the optimization of the above generator and discriminator. AN-GCN can classify nodes without taking their position as input. It is demonstrated that the AN-GCN is secure against edge-perturbing attacks in node classification tasks, as AN-GCN classifies nodes without the edge information and thus makes it impossible for attackers to perturb edges anymore. Extensive evaluations demonstrated the effectiveness of the general edge-perturbing attack model in manipulating the classification results of the target nodes. More importantly, the proposed AN-GCN can achieve 82.7% in node classification accuracy without the edge-reading permission, which outperforms the state-of-the-art GCN.

Introduction

Graph Convolutional Networks (GCNs) have become a standard tool for node classification tasks. However, their reliance on the graph Laplacian—a matrix derived directly from the graph's edges—introduces a significant security vulnerability. Attackers can manipulate the model's output by strategically adding or deleting a small number of edges, a process known as an edge-perturbing attack.

Overview of the edge-perturbing attack model (G-EPA) and its effect on node classification.

Traditional defenses, such as adversarial training or robust aggregation, attempt to filter out these malicious perturbations. However, as long as the model maintains "edge-reading permission," it remains susceptible to sophisticated attackers who can bypass these filters.

Theoretical Foundation: Node Localization

The core innovation of this work is the Node Localization Theorem. The authors mathematically demonstrate that GCNs use graph structure primarily to "locate" nodes within an embedding space. By treating node features as independent signals and mapping them to the Fourier domain, the model can unify disparate node signals into a single coordinate system.

Conversion of node features to a unified coordinate system via Fourier transform for node localization.

This insight suggests that if a model can determine node positions without reading the actual edges, it can become immune to edge-based attacks.

The AN-GCN Architecture

To implement this "anonymous" classification, the authors propose AN-GCN, which utilizes a generative adversarial framework:

  1. Staggered Gaussian Noise Generator: Instead of relying on the adjacency matrix, the model generates synthetic node positions from noise. A staggered distribution ensures nodes are distinguishable without overlapping on the coordinate axis.
  2. Spectral GCN Discriminator: This component serves as the classifier, attempting to categorize nodes correctly based solely on the generated positions and node features.
  3. Adversarial Optimization: The generator and discriminator are trained together. The generator learns to produce positions that maximize classification accuracy, effectively decoupling the classification process from the physical graph edges.

Experimental Results

The effectiveness of AN-GCN was evaluated on the Cora and Citeseer citation networks.

  • Attack Resilience: The proposed general edge-perturbing attack (G-EPA) was shown to flip the classification of up to 72.8% of nodes in models protected by existing state-of-the-art defenses.
  • Classification Performance: Despite having no access to edge information, AN-GCN achieved a classification accuracy of 82.7% on the Cora dataset, outperforming standard GCNs in several test scenarios.
  • Robustness under Meta-Attack: In high-perturbation environments where standard GCN accuracy dropped below 48%, AN-GCN maintained a stable performance, only decreasing from approximately 82% to 77%.

Conclusion

AN-GCN represents a paradigm shift in GCN security by advocating for "anonymity" as a defense mechanism. By withdrawing edge-reading permissions, the model fundamentally disarms edge-perturbing attackers. While future work is needed to address poisoning attacks and improve computational scalability for massive graphs, AN-GCN provides a robust and theoretically grounded solution for secure node classification.

Summary updated

Abstract

Recent studies have revealed the vulnerability of graph convolutional networks (GCNs) to edge-perturbing attacks, such as maliciously inserting or deleting graph edges. However, a theoretical proof of such vulnerability remains a big challenge, and effective defense schemes are still open issues. In this paper, we first generalize the formulation of edge-perturbing attacks and strictly prove the vulnerability of GCNs to such attacks in node classification tasks. Following this, an anonymous graph convolutional network, named AN-GCN, is proposed to counter against edge-perturbing attacks. Specifically, we present a node localization theorem to demonstrate how the GCN locates nodes during its training phase. In addition, we design a staggered Gaussian noise based node position generator, and devise a spectral graph convolution based discriminator in detecting the generated node positions. Further, we give the optimization of the above generator and discriminator. AN-GCN can classify nodes without taking their position as input. It is demonstrated that the AN-GCN is secure against edge-perturbing attacks in node classification tasks, as AN-GCN classifies nodes without the edge information and thus makes it impossible for attackers to perturb edges anymore. Extensive evaluations demonstrated the effectiveness of the general edge-perturbing attack model in manipulating the classification results of the target nodes. More importantly, the proposed AN-GCN can achieve 82.7% in node classification accuracy without the edge-reading permission, which outperforms the state-of-the-art GCN.
BibTeX
@misc{liu2020gcn,
  author = {Ao Liu and Beibei Li and Tao Li and Pan Zhou and Rui Wang},
  title = {{AN-GCN: An Anonymous Graph Convolutional Network Defense Against Edge-Perturbing Attack}},
  year = {2020},
  eprint = {2005.03482},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.03482},
}
Figure