Efficient Low-Rank GNN Defense Against Structural Attacks

Abdullah Alchihabi, Qing En, Yuhong Guo

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 the low-rank adjacency matrix estimation, which serves as a 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 with the GNN model. Sparsity is incorporated into 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.

Introduction

Graph Neural Networks (GNNs) have revolutionized the analysis of non-Euclidean data, yet their susceptibility to adversarial perturbations remains a significant hurdle for deployment in security-critical applications. Structural adversarial attacks—where an attacker strategically adds or removes edges—can drastically reduce a model's predictive accuracy. Current defense strategies generally face a trade-off: pre-processing methods like GCN-SVD are computationally efficient but lack the depth to counter sophisticated global attacks, while joint-optimization methods like Pro-GNN offer robustness but suffer from extreme computational overhead due to the optimization of dense $N \times N$ adjacency matrices.

This paper introduces ELR-GNN, a framework designed to bridge this gap. By representing the graph structure through low-rank factors and employing a dual-stage estimation process, ELR-GNN achieves state-of-the-art robustness while maintaining a computational profile that is orders of magnitude faster than existing joint-optimization techniques.

The ELR-GNN Framework

The core philosophy of ELR-GNN is that adversarial noise typically resides in the high-rank components of a graph's adjacency matrix. By constraining the model to a low-rank approximation, we can effectively filter out this noise. The framework operates in two distinct phases:

1. Coarse Low-Rank Estimation

To avoid the pitfalls of random initialization, the model begins with a truncated Singular Value Decomposition (SVD). By extracting the top $d$ singular values and vectors, the framework creates an initial "denoised" adjacency matrix. This step provides a mathematically grounded starting point that captures the essential global structure of the graph while discarding high-frequency perturbations often introduced by attackers.

2. Fine-Grained Estimation and Joint Learning

Unlike static pre-processing methods, ELR-GNN treats the low-rank factors as learnable parameters. The adjacency matrix is represented as a product of low-dimensional factors ($U_d$), which significantly reduces the parameter space from $O(N^2)$ to $O(Nd)$.

The model utilizes an alternating optimization strategy during training:

  • GNN Update: The graph structure is held fixed while the GNN weights are updated to minimize classification loss.
  • Graph Refinement: The GNN weights are held fixed while the singular vector matrix ($U_d$) is updated. This update minimizes a composite loss function that balances classification accuracy, a similarity penalty to keep the graph grounded in the original data, and a Frobenius norm regularizer for stability.

To further enhance efficiency and reflect the inherent sparsity of real-world networks, the framework applies sparsity pruning. Edges with weights below a specific threshold $\epsilon$ are removed, ensuring the model focuses on the most informative connections.

Experimental Results

The authors evaluated ELR-GNN against several benchmarks, including Cora, CiteSeer, and PolBlogs. The latter is a particularly rigorous test of structural defense, as it lacks node features, forcing the model to rely entirely on the link structure.

Robustness and Accuracy

ELR-GNN demonstrated superior resilience against "Mettack" (a global poisoning attack). On the PolBlogs dataset with a 25% attack rate, ELR-GNN achieved an accuracy of 76.7%, significantly outperforming Pro-GNN-fs, which reached only 63.1%. This suggests that the joint learning of low-rank factors is highly effective at recovering the underlying signal from heavily poisoned graphs.

Computational Efficiency

The most striking result is the efficiency gain. On the Cora dataset, ELR-GNN completed training in 118 seconds, compared to over 67,000 seconds for Pro-GNN—a 560x speedup. This efficiency makes joint-optimization defense viable for larger datasets where previous methods were computationally prohibitive.

Conclusion

ELR-GNN effectively addresses the robustness-efficiency dilemma in GNN defense. By combining the strengths of SVD-based initialization with the flexibility of joint optimization, it provides a scalable solution against structural attacks. Future work may explore dynamic rank selection and the application of these low-rank principles to evasion attacks at test-time, further hardening GNNs against adversarial environments.

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 the low-rank adjacency matrix estimation, which serves as a 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 with the GNN model. Sparsity is incorporated into 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},
}
Figure