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

• URL: http://arxiv.org/abs/2505.12437v2
• Date: Wed, 29 Oct 2025 15:09:38 GMT
• Title: A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring
• Authors: Michele Fontanesi, Alessio Micheli, Marco Podda, Domenico Tortorella,
• Abstract summary: Graph neural networks have become the de facto model for learning from structured data.<n>Several explainable AI techniques for graphs have been developed to address this major issue.<n>Current graph-XAI benchmarks are limited to simplistic synthetic datasets or a few real-world tasks curated by domain experts.<n>We propose a method to automate the construction of graph XAI benchmarks from generic graph classification datasets.
• Score: 4.187844916497259
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Semi-supervised Instruction Tuning for Large Language Models on Text-Attributed Graphs [62.544129365882014]
  We propose a novel Semi-supervised Instruction Tuning pipeline for Graph Learning, named SIT-Graph.<n> SIT-Graph is model-agnostic and can be seamlessly integrated into any graph instruction tuning method that utilizes LLMs as the predictor.<n>Extensive experiments demonstrate that when incorporated into state-of-the-art graph instruction tuning methods, SIT-Graph significantly enhances their performance on text-attributed graph benchmarks.
  arXiv  Detail & Related papers  (2026-01-19T08:10:53Z)
• Rethinking Graph-Based Document Classification: Learning Data-Driven Structures Beyond Heuristic Approaches [21.922739597512955]
  We propose a method to learn data-driven graph structures, eliminating the need for manual design and reducing domain dependence.<n>Our approach constructs homogeneous weighted graphs with sentences as nodes, while edges are learned via a self-attention model that identifies dependencies between sentence pairs.
  arXiv  Detail & Related papers  (2025-07-18T12:05:54Z)
• B-XAIC Dataset: Benchmarking Explainable AI for Graph Neural Networks Using Chemical Data [4.945980414437814]
  B-XAIC is a novel benchmark constructed from real-world molecular data and diverse tasks with known ground-truth rationales for assigned labels.<n>This benchmark provides a valuable resource for gaining deeper insights into the faithfulness of XAI, facilitating the development of more reliable and interpretable models.
  arXiv  Detail & Related papers  (2025-05-28T11:40:48Z)
• Rethinking Link Prediction for Directed Graphs [73.36395969796804]
  Link prediction for directed graphs is a crucial task with diverse real-world applications.<n>Recent advances in embedding methods and Graph Neural Networks (GNNs) have shown promising improvements.<n>We propose a unified framework to assess the expressiveness of existing methods, highlighting the impact of dual embeddings and decoder design on directed link prediction performance.
  arXiv  Detail & Related papers  (2025-02-08T23:51:05Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• AutoG: Towards automatic graph construction from tabular data [60.877867570524884]
  We aim to formalize the graph construction problem and propose an effective solution.<n>Existing automatic construction methods can only be applied to some specific cases.<n>We present a set of datasets to formalize and evaluate graph construction methods.<n>Second, we propose an LLM-based solution, AutoG, automatically generating high-quality graph schemas.
  arXiv  Detail & Related papers  (2025-01-25T17:31:56Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• An Automatic Graph Construction Framework based on Large Language Models for Recommendation [49.51799417575638]
  We introduce AutoGraph, an automatic graph construction framework based on large language models for recommendation.<n>LLMs infer the user preference and item knowledge, which is encoded as semantic vectors.<n>Latent factors are incorporated as extra nodes to link the user/item nodes, resulting in a graph with in-depth global-view semantics.
  arXiv  Detail & Related papers  (2024-12-24T07:51:29Z)
• Boosting Graph Neural Network Expressivity with Learnable Lanczos Constraints [7.605749412696919]
  Graph Neural Networks (GNNs) excel in handling graph-structured data but often underperform in link prediction tasks.<n>We present a novel method to enhance the expressivity of GNNs by embedding induced subgraphs into the graph Laplacian matrix's eigenbasis.<n>We demonstrate the ability to distinguish graphs that are indistinguishable by 2-WL, while maintaining efficient time complexity.
  arXiv  Detail & Related papers  (2024-08-22T12:22:00Z)
• Rethinking the Effectiveness of Graph Classification Datasets in Benchmarks for Assessing GNNs [7.407592553310068]
  We propose an empirical protocol based on a fair benchmarking framework to investigate the performance discrepancy between simple methods and GNNs. We also propose a novel metric to quantify the dataset effectiveness by considering both dataset complexity and model performance. Our findings shed light on the current understanding of benchmark datasets, and our new platform could fuel the future evolution of graph classification benchmarks.
  arXiv  Detail & Related papers  (2024-07-06T08:33:23Z)
• SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
  Graph neural networks (GNNs) have revolutionized the field of machine learning on non-Euclidean data such as graphs and networks. We propose a concatenation-based graph convolution mechanism that injectively updates node representations. We also design a novel graph pooling module, called WL-SortPool, to learn important subgraph patterns in a deep-learning manner.
  arXiv  Detail & Related papers  (2024-04-21T13:11:59Z)
• Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks [17.71313964436965]
  A popular paradigm for the explainability of GNNs is to identify explainable subgraphs by comparing their labels with the ones of original graphs. This task is challenging due to the substantial distributional shift from the original graphs in the training set to the set of explainable subgraphs. We propose a novel method that generates proxy graphs for explainable subgraphs that are in the distribution of training data.
  arXiv  Detail & Related papers  (2024-02-03T05:19:02Z)
• Similarity-aware Positive Instance Sampling for Graph Contrastive Pre-training [82.68805025636165]
  We propose to select positive graph instances directly from existing graphs in the training set. Our selection is based on certain domain-specific pair-wise similarity measurements. Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
  arXiv  Detail & Related papers  (2022-06-23T20:12:51Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  Graph outlier detection is an emerging but crucial machine learning task with numerous applications. We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
  arXiv  Detail & Related papers  (2022-06-21T01:46:38Z)
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction [123.20238648121445]
  We propose a new self-supervised learning framework, Graph Information Aided Node feature exTraction (GIANT) GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information. We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Benchmark datasets.
  arXiv  Detail & Related papers  (2021-10-29T19:55:12Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Neural Network Attribution Methods for Problems in Geoscience: A Novel Synthetic Benchmark Dataset [0.05156484100374058]
  We provide a framework to generate attribution benchmark datasets for regression problems in the geosciences. We train a fully-connected network to learn the underlying function that was used for simulation. We compare estimated attribution heatmaps from different XAI methods to the ground truth in order to identify examples where specific XAI methods perform well or poorly.
  arXiv  Detail & Related papers  (2021-03-18T03:39:17Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  We propose a novel pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. In all setups tested, our method boosts the average score of base models by a large margin of 4.7 points, as well as consistently outperforms the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-10T14:48:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.