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.
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.
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