Study of Robustness of Complex Networks and Graph Neural Networks

Abstract

This thesis focuses on the study of robustness in terms of complex networks and graph neural networks (GNNs) from multiple perspectives. Robustness, the ability to tolerate potential perturbations and attacks, plays a critical role in characterizing the functionality of corresponding systems or methods. Complex networks have been widely utilized to model the complex relationships in our social systems. Moreover, GNNs are effective methods to tackle and analyze these network-based data based on the strong learning power of neighborhood aggregations. However, both complex networks and GNNs suffer various attacks since the attackers would like to influence their functionality by attacking the graph data. Therefore, our task is to comprehensively study the robustness of them from multiple perspectives.

First, we study the robustness of transmission networks from an optimization perspective. Specifically, we consider a heterogeneous transmission network consisting of hosts and routers. Compared to the previous work, which focuses on analyzing transmission capacity only, we further consider another important metric, namely the robustness of transmission networks. To solve this problem, we model the optimization of the above two metrics as a multi-objective optimization problem and propose a multi-objective evolutionary algorithm to optimize the robustness and transmission capacity of transmission networks simultaneously. In particular, a two-phase framework has been proposed to further balance the computational cost.

Second, we investigate the robustness of GNNs from an attacker perspective. Despite the great success of GNNs in various graph-related tasks, current GNNs are not robust to adversarial attacks from the data view, such as adding or removing links, modifying node features, etc. Therefore, to study the robustness of GNNs, we theoretically analyze the attack strength of different adversarial links by utilizing the noise propagation process to understand the neighborhood aggregation mechanism of GNNs. We propose the concept of noise to quantify the attack strength of each adversarial link on neighborhood aggregations. We then develop three attack strategies to investigate the robustness of GNNs based on the proposed noise. Moreover, considering the difficulty of directly modifying the original network in real-world scenarios, we propose an effective attack method via fake node injections. In particular, the proposed strategy achieves a much better imperceptibility property on both structure and feature domains than previous methods.

Third, we explore the robustness of GNNs from a defender perspective. Since malicious attacks are inevitable in real life, we need to develop corresponding defense methods to improve the robustness of GNNs. However, as long tail degree distribution properties widely exist in real-world networks, we empirically observe that current defense methods have a prediction bias on nodes with low degree due to the principle of neighborhood aggregation. Therefore, we propose a defense method considering the data augmentation technique to mitigate the prediction bias between the nodes with low and high degree. Moreover, to understand the robustness of specific types of GNNs, heterophilic GNNs, we further conduct an empirical study on reviewing and analyzing the impact of several key designs on the robustness of heterophilic GNNs. In particular, the effects of high-order neighbor, potential neighbor, ego-neighbor separation, and inter-layer combination designs are evaluated.

Finally, we present an initial study on analyzing the impact of topological properties of complex networks, such as ER random networks, SW small-world networks, BA scale-free networks, etc., on the performance of GNNs. As these networks widely exist in our daily life, the performance stability of GNNs among these types of data can be an indicator for evaluating the robustness of GNNs against random perturbations. To carry out this analysis, we first improve the classic network generation models by incorporating the label assignment to satisfy the homophily requirement. Then, we conduct comprehensive experiments to analyze the influence of topological properties on the performance of GNNs.

Date of Award	12 Jul 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Kong TSE (Supervisor)