Harnessing Trust in Directed Graphs: Redefining Robustness of Graph Learning

Zhichao Hou; Xitong Zhang; Wei Wang; Charu C. Aggarwal; Xiaorui Liu

cs.LGJun 3, 2023

Harnessing Trust in Directed Graphs: Redefining Robustness of Graph Learning

Authors: Zhichao Hou, Xitong Zhang, Wei Wang, Charu C. Aggarwal, Xiaorui Liu

Organizations: North Carolina State University · Michigan State University · Meta · IBM T.J. Watson Research Center

Abstract

Existing research on robust Graph Neural Networks (GNNs) focuses predominantly on undirected graphs, overlooking the trustworthiness inherent in the link directions of directed graphs. In this work, we analyze the limitations of current approaches from both the attack and defense perspectives and redefine the robustness of GNNs in directed graphs. From the attack side, we introduce a more realistic directed graph attack setting that addresses the shortcomings of existing attacks. From the defense side, we propose a simple yet effective message-passing framework that serves as a plug-in layer to strengthen GNN robustness while avoiding a false sense of robustness. Our findings show that the trust signals encoded in directed graphs can be harnessed to substantially improve the robustness of GNNs. When combined with existing defense strategies, the framework achieves state-of-the-art robust performance alongside strong clean accuracy against both transfer and adaptive attacks. These results point to a novel and promising direction for strengthening the robustness of graph deep learning.

Figures & tables

Figure 1. Large-scale link spam. Attackers can cheaply fabricate many fake in-links to a target node (black), whereas manipulating the target’s real out-links requires compromising its account and is far harder, motivating greater trust in out-links than in-links.

{\mathbf{S}}^{(k)}_{ij}=\left\{\begin{aligned} 1\quad&\text{with probability}\;{\mathbf{P}}^{(T)}_{ij}\\ 0\quad&\text{with probability}\;1-{\mathbf{P}}^{(T)}_{ij}\end{aligned}\right.

Algorithm 1 PGD attack under RDGA setting

Model $\backslash$ Budget	0%	25%		50%		100%
Model $\backslash$ Budget	Clean	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive
MLP	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4
GCN	89.5±6.1	66.0±9.7	66.0±9.7	40.5±8.5	40.5±8.5	12.0±6.4	12.0±6.4
GCN-RW (Ours)	86.5±6.3	86.5±6.3	52.0±8.1	86.5±6.3	28.0±4.6	86.5±6.3	10.5±5.7
APPNP	90.5±4.7	81.5±9.5	80.5±10.4	66.5±8.7	68.0±12.1	44.0±9.2	46.0±7.3
APPNP-RW (Ours)	85.5±6.5	85.5±6.5	30.0±7.7	85.5±6.5	15.0±3.9	85.0±6.3	11.5±3.2

Table 1. Accuracy (%) on Cora-ML under RDGA. With RW, our GCN-RW and APPNP-RW exhibit great robustness under transfer attack ( bold ), but suffer from catastrophic failures due to indirect attacks under stronger adaptive attacks ( red ).

Figure 2. Adversary behaviors. (a) Attack modes defined relative to the target node. (b) Attacking GCN: the adversary concentrates on direct 1-hop in-link attacks (96.32%). (c) Attacking GCN-RW: direct in-link attacks are largely ineffective, so the adversary shifts to indirect 2-hop attacks via the target’s out-linking neighbors (65.55%), exposing GCN-RW’s false sense of robustness.

Panel of Figure 3 — Figure 3. Theoretical analysis of BBRW. (a) Direct attack ( $x_{2}\ tot$ ) vs. indirect attack ( $x_{1}\to z\to t$ ) considered in Theorem A.1, which derives the optimal bias weight $\beta^{*}$ that minimizes the worse-case attack influence. (b) Distribution of $\log k$ over 10,000 sampled node triplets from Cora-ML (black histogram) and the corresponding theoretical $\beta^{*}(k)$ (blue curve). The median $\beta^{*}=0.79$ with 80% confidence interval $(0.68,0.92)$ , matching the empirically optimal $\beta$ in Section 4.3.

Method	0%	25%		50%		100%
Method	Clean	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive
MLP	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4	73.5±7.4
DGCN	89.5±7.6	76.5±13.0	$\backslash$	54.5±7.9	$\backslash$	38.0±14.2	$\backslash$
DiGCN	85.0±7.4	50.0±6.7	$\backslash$	40.5±9.1	$\backslash$	29.0±6.2	$\backslash$
MagNet	88.5±3.2	70.5±10.6	$\backslash$	59.5±10.6	$\backslash$	54.0±7.0	$\backslash$
Jaccard-GCN	90.5±6.5	69.5±7.9	65.5±7.9	44.0±6.2	34.0±7.0	21.0±7.0	8.0±4.6

Table 2. Classification accuracy (%) under different perturbation rates of graph attack. The best results are in bold , and the second-best results are underlined . (Cora-ML)

Method	0%	25%		50%		100%
Method	Clean	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive
MLP	49.0±9.4	49.0±9.4	49.0±9.4	49.0±9.4	49.0±9.4	49.0±9.4	49.0±9.4
DGCN	64.0±7.0	54.0±8.3	$\backslash$	34.5±10.6	$\backslash$	27.0±10.1	$\backslash$
DiGCN	66.0±8.6	41.5±10.5	$\backslash$	29.5±8.2	$\backslash$	21.5±5.9	$\backslash$
MagNet	68.0±6.0	51.5±11.2	$\backslash$	35.0±12.0	$\backslash$	35.0±7.7	$\backslash$
Jaccard-GCN	57.0±7.1	45.5±7.9	38.5±9.5	23.0±7.8	11.5±5.5	20.0±10.2	6.5±5.0

Table 3. Classification accuracy (%) under different perturbation rates of graph attack. The best results are in bold , and the second-best results are underlined . (Citeseer)

Figure 4. Adversary behaviors against BBRW-SoftMedian (

\beta=0.7

). (a) Transfer: adversary focuses on direct 1-hop in-link attacks (96.32%), barely affecting BBRW-SoftMedian. (b) Adaptive: adversary shifts budget to indirect 2-hop (14.01%) and other attacks, yet accuracy stays at 87%.

Figure 5. Ablation study of $\beta$ on Cora-ML under transfer and adaptive attacks. Colors denote classification accuracy at different attack budgets. Increasing $\beta$ generally improves robustness under transfer attacks. Under adaptive attacks, accuracy increases with $\beta$ , peaks around $\beta=0.8$ , and then drops at $\beta=1$ , especially under larger attack budgets, highlighting the importance of balancing the trust assigned to in-links and out-links.

Figure 6. Ablation study of $\beta$ on Citeseer under transfer and adaptive attacks. Colors denote classification accuracy at different attack budgets. Increasing $\beta$ generally improves robustness under transfer attacks. Under adaptive attacks, performance peaks around $\beta=0.7$ – $0.8$ and declines as $\beta$ approaches $1$ , particularly under larger attack budgets, further demonstrating the need to balance the trust assigned to in-links and out-links.

Panel of Figure 7 — Figure 7. Robustness evaluation across various attack settings and datasets. (a) BBRW provides stronger robustness as more target out-links are protected. (b) BBRW consistently improves the backbone models under global attacks. (c) BBRW achieves stronger certified robustness across different perturbation budgets. (d) BBRW remains effective on larger citation networks with more complex structures. (e) BBRW mitigates the impact of adversarial edges introduced through node injection. (f) BBRW consistently improves robustness on datasets beyond citation networks.

	0%	25%	50%	100%
RDGA	61.5±7.4	43.0±10.3	27.0±14.4	20.5±9.6
Indirect	61.5±7.4	60.0±8.4	46.0±10.7	35.0±7.1

Table 4. Accuracy (%) of BBRW-GCN under RDGA and indirect attacks. RDGA consistently results in lower accuracy as the attack budget increases, demonstrating its greater attack strength.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Attack $\backslash$ Model	BBRW-GCN	BBRW-APPNP	BBRW-SoftMedian
RDGA-FGA	84.5±6.5	85.0±7.1	91.5±5.9
RDGA-Nettack	88.0±6.0	84.5±6.1	89.0±5.4
RDGA-PGD	85.0±6.3	83.0±6.4	88.0±5.1

Appendix

Table 5. Classification accuracy (%) under different attacks (Cora-ML, budget=50%)

Attack $\backslash$ Model	BBRW-GCN	BBRW-APPNP	BBRW-SoftMedian
RDGA-FGA	77.0±10.1	77.0±6.4	92.0±6.4
RDGA-Nettack	85.5±7.2	79.0±6.6	86.5±6.7
RDGA-PGD	75.0±10.2	69.0±9.7	84.5±8.8

Appendix

Table 6. Classification accuracy (%) under different attacks (Cora-ML, budget=100%)

Method	5%		10%		15%		20%
Method	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive
MLP	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4	73.5 $\pm$ 7.4
DGCN	87.0 $\pm$ 8.7	$\backslash$	84.5 $\pm$ 9.8	$\backslash$	81.5 $\pm$ 10.8	$\backslash$	79.0 $\pm$ 11.9	$\backslash$
DiGCN	78.0 $\pm$ 7.3	$\backslash$	71.0 $\pm$ 7.1	$\backslash$	64.0 $\pm$ 7.0	$\backslash$	57.0 $\pm$ 6.8	$\backslash$
MagNet	88.0 $\pm$ 3.3	$\backslash$	86.5 $\pm$ 3.9	$\backslash$	85.0 $\pm$ 5.5	$\backslash$	78.5 $\pm$ 8.1	$\backslash$
Jaccard-GCN	86.5 $\pm$ 6.8	82.5 $\pm$ 6.8	82.0 $\pm$ 7.1	78.0 $\pm$ 7.1	78.0 $\pm$ 7.3	74.0 $\pm$ 7.3	73.5 $\pm$ 7.6	69.5 $\pm$ 7.6

Appendix

Table 7. Classification accuracy (%) under different perturbation rates of graph attack. The best results are in bold , and the second-best results are underlined . (Cora-ML)

Method	5%		10%		15%		20%
Method	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive	Transfer	Adaptive
MLP	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4	49.0 $\pm$ 9.4
DGCN	62.0 $\pm$ 7.3	\	60.0 $\pm$ 7.5	\	58.0 $\pm$ 7.8	\	56.0 $\pm$ 8.0	\
DiGCN	61.0 $\pm$ 9.0	\	56.0 $\pm$ 9.4	\	51.5 $\pm$ 9.7	\	46.5 $\pm$ 10.1	\
MagNet	64.5 $\pm$ 7.0	\	61.5 $\pm$ 8.1	\	58.0 $\pm$ 9.1	\	55.0 $\pm$ 10.2	\
Jaccard-GCN	55.0 $\pm$ 7.3	53.5 $\pm$ 7.6	52.5 $\pm$ 7.4	50.0 $\pm$ 8.1	50.0 $\pm$ 7.6	46.0 $\pm$ 8.6	48.0 $\pm$ 7.7	42.0 $\pm$ 9.1

Appendix

Table 8. Classification accuracy (%) under different perturbation rates of graph attack. The best results are in bold , and the second-best results are underlined . (Citeseer)

Figure 8. Masking rates under transfer attack.

Figure 9. Distributions of adversarial links against different victim models (GCN and GCN-RW) under different attack budgets (25%, 50%, 100%). The yellow portion represents attacks by 1-hop neighbors on the target (direct in-link attacks); the red portion represents attacks by 2-hop neighbors on the targets’ neighbors (indirect out-link attacks); and the blue portion represents other attacks.

Graph Neural Networks

Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.

See all 714 papers

Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks
Jun 2, 2026Anubha Goel, Juho KanniainenGraph Structure Learning Graph Neural Networks
Computing Science/Financial Computing and Data Analytics Group, Tampere University, Tampere, 33720, Finland
GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks
Jun 1, 2026Canyixing Cui, Tao Wu, Xingping Xian +3Disentangled Representation Learning Graph Neural Networks
School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, China · School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications, Chongqing, China · Computational Communication Research Center, Beijing Normal University, Zhuhai, China +2
Adversarial Attacks on Locally Private Graph Neural Networks
Mar 21, 2026Matta Varun, Ajay Kumar Dhakar, Yuan Hong +1Adversarial Attacks Graph Neural Networks
Indian Institute of Technology Kharagpur, India · University of Connecticut, USA

Jun 2, 2026J/K move · Enter open · S save

Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks

Anubha Goel, Juho Kanniainen

Computing Science/Financial Computing and Data Analytics Group, Tampere University, Tampere, 33720, Finland

Graph Structure Learning Graph Neural Networks Graph Robustness

Open paper AskPDF arXiv

Graph neural networks have achieved strong performance on graph-structured data, but their effectiveness depends heavily on the quality of the observed graph. In real applications, graph topology is often imperfect: noisy edges may connect unrelated nodes, while missing edges may prevent useful information from being propagated. Existing robust graph learning methods mainly address this problem by removing suspicious edges or by learning a new graph structure during training. However, edge removal alone cannot recover missing connections, and graph structure learning may introduce additional optimization complexity. In this paper, we propose Topology-Aware Gaussian Repair (TAGR), a simple graph repair framework for robust message passing in graph neural networks. Instead of learning a dense adjacency matrix, TAGR constructs a sparse feature-neighborhood graph using an adaptive Gaussian kernel and combines it with a topology-aware residual correction of the observed graph. The Gaussian repair component introduces auxiliary edges between feature-similar nodes, while the residual correction preserves and reweights the original topology according to local feature and structural consistency. The repaired graph can be used directly with standard graph neural networks without changing their architectures. Extensive experiments on benchmark citation networks show that TAGR improves the robustness of GNNs under both noisy-edge and missing-edge settings. The analysis further show that Gaussian feature-neighborhood repair provides the main robustness gain, while topology-aware residual correction improves stability when the observed graph is incomplete. These results suggest that effective graph robustness can be achieved through lightweight sparse graph repair rather than dense graph structure learning.

Abstract

Graph Neural Networks

Explore similar work

Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks

GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks

Adversarial Attacks on Locally Private Graph Neural Networks