Explainability in Deep Graph Networks: Inductive Bias Analysis and New Benchmarks

Deep Graph Networks (DGNs) have emerged as the most prominent methodology for processing graph-structured data, achieving remarkable performance on predictive tasks. However, DGNs' inductive biases, the set of assumptions that allow for generalising to unseen data, are obscured by many human-unintelligible parameters; thereby raising concerns about their reliability and compromising their adoption due to conflicts with regulatory frameworks, such as the EU AI Act. The field of Graph Explainable AI (GXAI) seeks to bridge this gap with graph explainers, techniques highlighting graph structures driving DGNs' predictions. Progress, however, is hindered by a lack of standardised evaluation protocols and challenging benchmarks. Consequently, achieving DGNs' explainability and constructing explainable and reliable DGN frameworks remain a non-trivial challenge, impeded by our limited grasp of DGN generalisation mechanics and the uncertainty regarding the efficacy of graph explainers in real-world scenarios. To address these impediments, this thesis operates at the intersection of Machine Learning for graph-structured data and GXAI by focusing on two primary objectives: characterising the inductive biases of DGNs and establishing a robust benchmarking ecosystem for graph explainers.