Efficient Low-Rank GNN Defense Against Structural Attacks

Abdullah Alchihabi, Qing En, Yuhong Guo

This paper, titled "Efficient Low-Rank GNN Defense Against Structural Attacks," introduces a novel framework called ELR-GNN. It aims to solve the "robustness-efficiency" trade-off in Graph Neural Networks (GNNs) by learning a cleaned, low-rank, and sparse version of a poisoned graph structure during training.

TL;DR

ELR-GNN defends Graph Neural Networks against structural adversarial attacks by jointly learning a low-rank, sparse approximation of the adjacency matrix alongside the GNN model. It achieves state-of-the-art robustness while being up to 560x faster than previous joint-optimization defense methods.

What Problem Does This Paper Address?

Graph Neural Networks are notoriously fragile. Even "imperceptible" changes to a graph’s structure—adding or deleting a few strategic edges—can cause a GNN's performance to plummet. These are known as structural adversarial attacks.

Existing defenses generally fall into two camps:

  1. Pre-processing methods: These (like GCN-SVD) filter the graph before training. They are fast but often fail against sophisticated "global" attacks because the cleaning step is decoupled from the learning task.
  2. Joint-optimization methods: These (like Pro-GNN) try to learn a "clean" graph and the GNN parameters simultaneously. While robust, they are computationally expensive because they typically optimize a dense $N \times N$ adjacency matrix, making them impractical for large-scale graphs.

The authors address the need for a defense that is both highly robust against poisoning attacks (where the training data itself is tampered with) and computationally efficient.

Methods

The core idea of ELR-GNN is to represent the adjacency matrix not as a massive $N \times N$ grid, but as a product of low-dimensional factors. The framework consists of two modules:

  1. Coarse Low-Rank Estimation: Adversarial attacks typically target the high-rank (low-valued) singular components of a graph's adjacency matrix. To counter this, the authors use Truncated Singular Value Decomposition (SVD) to extract only the top $d$ singular values and vectors. This provides a "denoised" starting point for the graph structure.

  2. Fine-Grained Estimation: Instead of keeping the SVD result static, ELR-GNN refines it. It treats the singular vector matrix ($U_d$) as a learnable parameter. During training, it uses an alternating optimization strategy:

  3. Update GNN: Fix the graph structure and update the GNN weights to minimize classification loss.

  4. Update Graph: Fix the GNN and update the singular vectors ($U_d$) to minimize a combined loss that includes classification error, a similarity penalty (keeping the learned graph close to the original), and a Frobenius norm regularizer.

To maintain efficiency and mimic real-world graphs, the authors also apply sparsity pruning, deleting weak edges with weights below a threshold $\epsilon$.

Datasets

The authors evaluated their method on three standard benchmarks:

  • Cora & CiteSeer: Common citation networks where nodes are papers and edges are citations.
  • PolBlogs: A network of political blogs. This is a particularly "pure" structural test because it contains no node features—only the graph's link structure.

Key Insights and Ideas

  • Low-Rank as a Filter: By restricting the GNN to a low-rank version of the adjacency matrix, the model naturally ignores the high-rank "noise" introduced by attackers.
  • Factorization for Speed: By optimizing the low-rank factors ($N \times d$) instead of the full adjacency matrix ($N \times N$), the number of parameters to optimize drops significantly. This is the primary driver behind the massive speedup.
  • Joint Learning is Essential: The ablation studies show that "Rand. Init." (randomly initializing the graph structure) performs poorly. Starting with a coarse SVD estimate and then refining it jointly with the GNN is the "secret sauce" for high accuracy.

Key Results

  • Superior Robustness: ELR-GNN consistently outperformed or matched state-of-the-art defenses (like Pro-GNN and SimP-GCN) across all datasets. On the PolBlogs dataset under a 25% attack rate, ELR-GNN achieved 76.7% accuracy, while the next best joint-optimization method (Pro-GNN-fs) trailed at 63.1%.
  • Massive Efficiency Gains: This is the paper's standout result. On the Cora dataset, ELR-GNN was 560 times faster than Pro-GNN (118 seconds total vs. over 67,000 seconds).
  • Resilience to Various Attacks: The model proved effective against global poisoning (Mettack), targeted attacks (Nettack), and random noise.

Limitations and Future Work

  • Hyperparameter Tuning: The performance depends on choosing the right rank ($d$) and sparsity threshold ($\epsilon$). While the authors use cross-validation, finding these values for massive, novel datasets could be time-consuming.
  • Static Rank: The rank $d$ is fixed at the start. A more flexible approach might involve learning the optimal rank dynamically during training.
  • Scope: The study focuses primarily on poisoning attacks. While structural defenses often carry over to evasion (test-time) attacks, the paper does not provide extensive benchmarks for that specific scenario.

Summary updated

Abstract

Graph Neural Networks (GNNs) have been shown to possess strong representation abilities over graph data. However, GNNs are vulnerable to adversarial attacks, and even minor perturbations to the graph structure can significantly degrade their performance. Existing methods either are ineffective against sophisticated attacks or require the optimization of dense adjacency matrices, which is time-consuming and prone to local minima. To remedy this problem, we propose an Efficient Low-Rank Graph Neural Network (ELR-GNN) defense method, which aims to learn low-rank and sparse graph structures for defending against adversarial attacks, ensuring effective defense with greater efficiency. Specifically, ELR-GNN consists of two modules: a coarse low-rank estimation module and a fine-grained estimation module. The first module adopts the truncated Singular Value Decomposition (SVD) to initialize a low-rank estimate of the adjacency matrix, which serves as the starting point for optimizing the low-rank matrix. In the second module, the initial estimate is refined by jointly learning a low-rank sparse graph structure together with the GNN model. Sparsity is enforced on the learned low-rank adjacency matrix by pruning weak connections, which can reduce redundant data while maintaining valuable information. As a result, instead of using the dense adjacency matrix directly, ELR-GNN can learn a low-rank and sparse estimate of it in a simple, efficient, and easy to optimize manner. The experimental results demonstrate that ELR-GNN outperforms the state-of-the-art GNN defense methods in the literature, in addition to being very efficient and easy to train.
BibTeX
@inproceedings{alchihabi2023efficient,
  author = {Abdullah Alchihabi and Qing En and Yuhong Guo},
  title = {{Efficient Low-Rank GNN Defense Against Structural Attacks}},
  booktitle = {ICKG},
  year = {2023},
  url = {https://openreview.net/forum?id=gpvOl6VhN1},
}

Loading related content...

Figure