Toward Interpretable Graph Classification via Concept-Focused Structural Correspondence

Despite significant achievements in numerous real-world applications, the black-box nature hinders GNNs from being adopted in high-stake decision situations. This paper introduces an advanced interpretable graph classification approach grounded on concept-focused structural correspondence. Our method harnesses the inherent interpretability of the case-based reasoning methodology and utilizes the Earth Mover’s Distance (EMD) to determine structural similarities between graphs. Enhanced by a concept-centric node-weighting scheme, our refined EMD prioritizes nodes within frequently observed essential subgraphs. The enhanced EMD metric is pivotal to our interpretable non-parametric predictor, which utilizes it to derive predictions based on the proximity of input graphs to reference graphs. A dual-phase strategy ensures efficiency by selecting references using Euclidean distance and refining via EMD. Our framework integrates various explanation modalities catering to diverse needs for prediction explanations, elucidating the model’s decision-making processes. Empirical evaluations and a specific user study affirm our approach’s robustness and applicability.