Méthodes d'explication basées sur la théorie des jeux pour les réseaux de neurones sur graphes

Graph Neural Networks (GNNs) have achieved remarkable success across a wide range of applications. However, their complex architectures make them difficult to interpret, limiting their adoption in critical domains where transparency is essential. Although many explanation methods have been proposed for GNNs, most lack theoretical guarantees regarding the faithfulness and reliability of their outputs. Among these methods, game-theoretic approaches stand out by offering formal guarantees, grounded in well-established axioms. Most game-theoretic methods define the input components (e.g., nodes or edges) as players and compute their contributions in a cooperative game using solution concepts such as Shapley values or HN-values. However, the exact computation of contribution values is exponential in the number of players, making the use of exact solutions computationally infeasible for large graphs. Consequently, approximation methods are often employed. Nevertheless, as the size of the input graph increases, the quality of these approximations deteriorates, undermining the reliability of the explanations. To address these challenges, this thesis proposes two complementary solutions. First, we introduce a method called INSIDE-SHAP that uses activation rules, derived from hidden representations of GNNs, as players in the cooperative game. INSIDE-SHAP decouples the size of the player set from the size of the input graph, enabling more efficient computation of Shapley-based contributions without sacrificing theoretical guarantees. Second, we present a novel game-theoretic framework (ESPAM) based on alternative axioms, distinct from those underpinning Shapley values. This framework permits exact polynomial-time computation of contribution values, thereby eliminating the need for approximations while preserving structural dependencies within the graph. Furthermore, the proposed method is model-agnostic, enhancing its applicability across diverse GNN architectures. Finally, we demonstrate the practical utility of ESPAM by applying it to a complex GNN model for molecule-drug interaction prediction. Together, these contributions advance the development of scalable, faithful, and theoretically grounded explanations for GNN models.