# A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring

arXiv: https://arxiv.org/abs/2505.12437 · HTML: https://mlsanity.com/paper/2505.12437/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 58 references that are in the map.
- First posted on arXiv 18 May 2025.

## Builds on (most cited first, 28 of 28)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Learning Deep Features for Discriminative Localization](https://mlsanity.com/paper/1512.04150/) (2015)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Devign: Effective Vulnerability Identification by Learning Comprehensive Program Semantics via Graph Neural Networks](https://mlsanity.com/paper/1909.03496/) (2019)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [On Structural Expressive Power of Graph Transformers](https://mlsanity.com/paper/2305.13987/) (2023)
- [The Iteration Number of Colour Refinement](https://mlsanity.com/paper/2005.10182/) (2020)
- [BAGEL: A Benchmark for Assessing Graph Neural Network Explanations](https://mlsanity.com/paper/2206.13983/) (2022)
- [On the approximation capability of GNNs in node classification/regression tasks](https://mlsanity.com/paper/2106.08992/) (2021)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Explainable Artificial Intelligence for Drug Discovery and Development -- A Comprehensive Survey](https://mlsanity.com/paper/2309.12177/) (2023)

## Abstract (arXiv)

Graph neural networks have become the de facto model for learning from structured data. However, the decision-making process of GNNs remains opaque to the end user, which undermines their use in safety-critical applications. Several explainable AI techniques for graphs have been developed to address this major issue. Focusing on graph classification, these explainers identify subgraph motifs that explain predictions. Therefore, a robust benchmarking of graph explainers is required to ensure that the produced explanations are of high quality, i.e., aligned with the GNN's decision process. However, current graph-XAI benchmarks are limited to simplistic synthetic datasets or a few real-world tasks curated by domain experts, hindering rigorous and reproducible evaluation, and consequently stalling progress in the field. To overcome these limitations, we propose a method to automate the construction of graph XAI benchmarks from generic graph classification datasets. Our approach leverages the Weisfeiler-Leman color refinement algorithm to efficiently perform approximate subgraph matching and mine class-discriminating motifs, which serve as proxy ground-truth class explanations. At the same time, we ensure that these motifs can be learned by GNNs because their discriminating power aligns with WL expressiveness. This work also introduces the OpenGraphXAI benchmark suite, which consists of 15 ready-made graph-XAI datasets derived by applying our method to real-world molecular classification datasets. The suite is available to the public along with a codebase to generate over 2,000 additional graph-XAI benchmarks. Finally, we present a use case that illustrates how the suite can be used to assess the effectiveness of a selection of popular graph explainers, demonstrating the critical role of a sufficiently large benchmark collection for improving the significance of experimental results.