Graph Neural Networks (GNNs) have emerged as the standard paradigm for machine learning on graph-structured data, demonstrating remarkable success in diverse applications such as molecular design, anomaly detection within networks, and recommendation systems. However, despite their effectiveness in learning meaningful representations for nodes and graphs, GNNs remain vulnerable to adversarial attacks. These attacks, which are small strategically crafted perturbations to the input graph, can result in unreliable predictions. This specific vulnerability raises serious concerns regarding the deployment of GNNs in safety-critical domains like finance and healthcare, where ensuring robustness is crucial. Consequently, understanding and enhancing the adversarial robustness of GNNs has become a critical research focus, involving both the design of potent attack strategies and the development of resilient defense mechanisms.
Many existing defense methods rely on pre-processing techniques or modifications to the message-passing framework to mitigate attacks, often by discarding or re-weighting parts of the input graph. Although these defenses have shown great results, they are frequently based on heuristic reasoning and lack strong theoretical guarantees. Specifically, given the input graphs' rich topological aspect, a deeper understanding of their vulnerabilities and internal behaviors is essential, especially regarding how an attack can propagate through the network. Moreover, current defense methodologies are typically evaluated only against the state-of-the-art attacks available at the evaluation time; in the absence of theoretical guarantees, these defenses remain susceptible to more advanced or previously unseen attack strategies. This gap underscores the need for mechanisms that not only exhibit robust empirical performance but also provide certifiable robustness for long-term effectiveness. Furthermore, most current approaches entail high computational overhead, limiting their practical feasibility in real-world applications.
In this thesis, we address key challenges in GNN adversarial robustness, focusing on the aforementioned drawbacks. First, we introduce defense mechanisms that are both empirically effective and grounded in solid theoretical analysis, thereby offering provable robustness against evolving attacks. Second, we investigate how to reconcile strong defense performance with computational efficiency, which is an essential requirement in multiple domains such as applications in the mobile and online platforms. Achieving this balance is critical for broadening the deployment of robust GNNs in practical settings. Finally, we explore often overlooked factors related to the training dynamics, such as weight initialization and the number of training epochs, that can substantially influence a model’s underlying robustness, illustrating how effective parameter selection can bolster resilience with very limited costs.
The contributions of this thesis are organized around four core pillars. In the first, we propose an adaptation of Graph Convolutional Networks (GCNs) using orthogonal weight matrices, showing both theoretically and empirically that this design can significantly enhance model robustness. In the second contribution, we present a simple yet powerful technique for injecting noise into hidden representations during training, which substantially improves robustness with minimal additional computational cost, consequently offering a more lightweight alternative to many existing, high-complexity defense methods. The third work examines the neglected interplay between training dynamics (e.g., number of epochs, initialization strategies) and model vulnerability, demonstrating how careful tuning of these parameters can enhance a model's underlying robustness. Finally, we propose a novel adversarial attack approach that generates adversarial graphs from scratch via a learnable generator, rather than merely perturbing existing graphs, thereby introducing new perspectives on attack methodologies.
Through these contributions, the current thesis aims to provide theoretical insights and tools that could help advance the current understanding of adversarial attacks in the context of GNNs. These contributions and insights can advance the development of robust GNNs, paving the way for safer and more reliable graph-based machine learning systems.