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.

Graph Neural Networks (GNNs) har etablerat sig som ett standardparadigm för maskininlärning på grafstrukturerad data och har visat stor framgång inom tillämpningar som molekyldesign, anomalidetektion i nätverk och rekommendationssystem. Trots deras förmåga att lära sig meningsfulla representationer för noder och grafer är GNNs sårbara för adversarial attacks, det vill säga små, strategiskt utformade perturbationer i indata som kan leda till opålitliga prediktioner. Denna sårbarhet väcker allvarliga farhågor vid användning i säkerhetskritiska domäner såsom finans och sjukvård, där robusthet är avgörande. Följaktligen har förståelsen och förbättringen av GNNs adversarial robustness blivit ett centralt forskningsområde, innefattande både utveckling av effektiva attackstrategier och motståndskraftiga försvarsmekanismer.

Många befintliga defense methods bygger på preprocessing-tekniker eller modifieringar av message passing-ramverket, ofta genom att filtrera eller omvikta delar av grafen. Trots god empirisk prestanda baseras dessa metoder ofta på heuristik och saknar starka teoretiska garantier. Givet grafernas rika topologiskastruktur krävs en djupare förståelse av deras sårbarheter och interna dynamik,särskilt hur en attack kan spridas genom nätverket. Dessutom utvärderas försvar vanligtvis endast mot state-of-the-art attacks vid utvärderingstillfället, vilket gör dem sårbara för mer avancerade eller tidigare okända strategier. Detta belyser behovet av metoder som kombinerar god empirisk prestanda med certifierbar robusthet. Samtidigt innebär många nuvarande angreppssätt hög computational overhead, vilket begränsar deras praktiska användbarhet.

Denna avhandling adresserar centrala utmaningar inom adversarial robustness för GNNs. För det första introduceras defense mechanisms som är både empiriskt effektiva och teoretiskt grundade, med provable robustness mot föränderliga attacker. För det andra undersöks hur stark defense performance kan förenas med computational efficiency, vilket är avgörande för tillämpningar i exempelvis mobila och onlinebaserade system. För det tredje analyseras ofta förbisedda faktorer i training dynamics, såsom weight initialization och antal training epochs,och hur dessa påverkar modellens robusthet, där noggrant parameterurval kan ge betydande förbätringar till låg kostnad.

Avhandlingens bidrag organiseras kring fyra huvudområden. För det första föreslås en modifiering av Graph Convolutional Networks (GCNs) med orthogonal weightmatrices som teoretiskt och empiriskt förbättrar robustheten. För det andra presenteras en enkel men effektiv metod för att injicera noise i hidden representations under träning, vilket ger ökad robusthet med låg computational cost. För det tredje analyseras samspelet mellan training dynamics och sårbarhet,vilket visar hur parametrisering påverkar robustheten. Slutligen introduceras en ny adversarial attackmetod där grafer genereras från grunden via en learnable generator, snarare än att enbart perturb befintliga grafer. Sammanfattningsvis bidrar avhandlingen med teoretiska insikter och praktiskaverktyg som fördjupar förståelsen av adversarial attacks i GNNs och främjar utvecklingen av mer robusta och tillförlitliga grafbaserade maskininlärningssystem.