Can Directed Graph Neural Networks be Adversarially Robust?

Zhichao Hou, Xitong Zhang, Wei Wang, Charu C. Aggarwal, Xiaorui LiuarXiv 2023 · DOI · arXiv

Introduction

Graph Neural Networks (GNNs) have become a cornerstone of machine learning on structured data, yet they remain notoriously fragile under adversarial attacks. Most research into GNN robustness treats graphs as undirected, where an edge is a simple bidirectional connection. However, real-world networks—such as social media follows, citation networks, and web hyperlinks—are inherently directed. This paper explores how the "trust" signals embedded in directed edges can be leveraged to build more resilient models.

The Problem: Asymmetric Trust in Directed Graphs

In a directed graph, there is a fundamental asymmetry in control. A user controls their out-links (who they follow), but cannot easily control their in-links (who follows them). This makes it much harder for an attacker to hijack a target's outgoing connections than to create thousands of fake "bot" accounts to point at a victim. Existing GNNs often ignore this by "symmetrizing" the graph, effectively throwing away this valuable trust information and leaving themselves vulnerable to adversarial noise.

Figure 1: Illustration of directed graph links and the attack scenario involving target, neighbors, and fake nodes.

Methodology

The authors propose two key innovations to address these vulnerabilities:

1. Restricted Directed Graph Attack (RDGA)

RDGA is a realistic adversarial setting that acknowledges the difficulty of manipulating a target's out-links. While standard attacks might flip any edge, RDGA focuses on the practical reality where an attacker can easily flood a victim with malicious in-links but has limited influence over the victim's own outgoing choices.

2. Biased Bidirectional Random Walk (BBRW)

BBRW is a universal "plug-in" message-passing layer designed to enhance any GNN backbone (e.g., GCN, APPNP). It aggregates information from both incoming and outgoing neighbors but introduces a bias hyperparameter ($\beta$) to weight them. By favoring out-links—which are inherently more reliable—BBRW maintains high classification accuracy even when in-links are heavily corrupted.

Key Insights: Balancing Trust and Indirect Attacks

A critical finding of the research is the "false sense of robustness" that comes from trusting only one direction. If a model exclusively trusts out-links, a direct attack on the target fails. However, a sophisticated "adaptive" attacker can instead target the neighbors of the victim. Since the victim trusts its neighbors' out-links, the corruption eventually flows through the graph. The BBRW framework solves this by maintaining a "Biased Bidirectional" approach, carefully weighting both directions to prevent catastrophic failure from these indirect paths.

Key Results

The BBRW framework demonstrates state-of-the-art robustness across multiple benchmarks, including Cora-ML and Citeseer.

Figure 6: Performance comparison of various GNN models under different attack budgets and strategies.

As shown in the results, the BBRW-GCN-Soft-Median variant is particularly effective. On the Cora-ML dataset, it maintained 84.5% accuracy under a 100% attack budget, whereas a standard GCN's performance collapsed to just 12%. Importantly, this robustness does not come at the cost of "clean" accuracy; BBRW models often match or exceed the performance of standard models on unperturbed data.

Conclusion

By acknowledging the inherent structure of directed graphs, this work provides a powerful new defense mechanism for GNNs. The BBRW layer offers a simple, universal way to boost robustness against both transfer and adaptive attacks without sacrificing general performance. Future work will look to extend these findings to poisoning attacks and larger, billion-scale networks.

Summary updated

Abstract

The existing research on robust Graph Neural Networks (GNNs) fails to acknowledge the significance of directed graphs in providing rich information about networks' inherent structure. This work presents the first investigation into the robustness of GNNs in the context of directed graphs, aiming to harness the profound trust implications offered by directed graphs to bolster the robustness and resilience of GNNs. Our study reveals that existing directed GNNs are not adversarially robust. In pursuit of our goal, we introduce a new and realistic directed graph attack setting and propose an innovative, universal, and efficient message-passing framework as a plug-in layer to significantly enhance the robustness of GNNs. Combined with existing defense strategies, this framework achieves outstanding clean accuracy and state-of-the-art robust performance, offering superior defense against both transfer and adaptive attacks. The findings in this study reveal a novel and promising direction for this crucial research area. The code will be made publicly available upon the acceptance of this work.
BibTeX
@misc{hou2023can,
  author = {Zhichao Hou and Xitong Zhang and Wei Wang and Charu C. Aggarwal and Xiaorui Liu},
  title = {{Can Directed Graph Neural Networks be Adversarially Robust?}},
  year = {2023},
  eprint = {2306.02002},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.02002},
}
Figure