TreeX: Generating Global Graphical GNN Explanations via Critical Subtree Extraction

• URL: http://arxiv.org/abs/2503.09051v1
• Date: Wed, 12 Mar 2025 04:36:28 GMT
• Title: TreeX: Generating Global Graphical GNN Explanations via Critical Subtree Extraction
• Authors: Shengyao Lu, Jiuding Yang, Baochun Li, Di Niu,
• Abstract summary: We propose to unbox GNNs by analyzing and extracting critical subtrees incurred by the inner workings of message passing.<n>By aggregating subtrees in an embedding space with an efficient algorithm, we can make intuitive graphical explanations for Message-Passing GNNs on local, class and global levels.
• Score: 38.99239532650183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The growing demand for transparency and interpretability in critical domains has driven increased interests in comprehending the explainability of Message-Passing (MP) Graph Neural Networks (GNNs). Although substantial research efforts have been made to generate explanations for individual graph instances, identifying global explaining concepts for a GNN still poses great challenges, especially when concepts are desired in a graphical form on the dataset level. While most prior works treat GNNs as black boxes, in this paper, we propose to unbox GNNs by analyzing and extracting critical subtrees incurred by the inner workings of message passing, which correspond to critical subgraphs in the datasets. By aggregating subtrees in an embedding space with an efficient algorithm, which does not require complex subgraph matching or search, we can make intuitive graphical explanations for Message-Passing GNNs on local, class and global levels. We empirically show that our proposed approach not only generates clean subgraph concepts on a dataset level in contrast to existing global explaining methods which generate non-graphical rules (e.g., language or embeddings) as explanations, but it is also capable of providing explanations for individual instances with a comparable or even superior performance as compared to leading local-level GNN explainers.

Related papers

• 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)
• Global Graph Counterfactual Explanation: A Subgraph Mapping Approach [54.42907350881448]
  Graph Neural Networks (GNNs) have been widely deployed in various real-world applications. Counterfactual explanation aims to find minimum perturbations on input graphs that change the GNN predictions. We propose GlobalGCE, a novel global-level graph counterfactual explanation method.
  arXiv  Detail & Related papers  (2024-10-25T21:39:05Z)
• Unveiling Global Interactive Patterns across Graphs: Towards Interpretable Graph Neural Networks [31.29616732552006]
  Graph Neural Networks (GNNs) have emerged as a prominent framework for graph mining. This paper proposes a novel intrinsically interpretable scheme for graph classification. Global Interactive Pattern (GIP) learning introduces learnable global interactive patterns to explicitly interpret decisions.
  arXiv  Detail & Related papers  (2024-07-02T06:31:13Z)
• The Intelligible and Effective Graph Neural Additive Networks [29.686091109844746]
  Graph Neural Additive Network (GNAN) is a novel extension of the interpretable class of Generalized Additive Models.<n>GNAN is designed to be fully interpretable, offering both global and local explanations at the feature and graph levels.<n>We demonstrate the intelligibility of GNANs in a series of examples on different tasks and datasets.
  arXiv  Detail & Related papers  (2024-06-03T13:29:36Z)
• EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time [30.44473492282072]
  Most existing subgraph-level explainers face efficiency challenges in explaining Graph Neural Networks (GNNs) due to complex search processes. In this paper, we reveal that inducing subgraph explanations by edges is more comprehensive than other subgraph inducing techniques. We employ an efficient linear-time search algorithm over the edge-induced subgraphs, where the edges are ranked by an enhanced gradient-based importance.
  arXiv  Detail & Related papers  (2024-05-02T21:55:12Z)
• DGNN: Decoupled Graph Neural Networks with Structural Consistency between Attribute and Graph Embedding Representations [62.04558318166396]
  Graph neural networks (GNNs) demonstrate a robust capability for representation learning on graphs with complex structures. A novel GNNs framework, dubbed Decoupled Graph Neural Networks (DGNN), is introduced to obtain a more comprehensive embedding representation of nodes. Experimental results conducted on several graph benchmark datasets verify DGNN's superiority in node classification task.
  arXiv  Detail & Related papers  (2024-01-28T06:43:13Z)
• Local Structure-aware Graph Contrastive Representation Learning [12.554113138406688]
  We propose a Local Structure-aware Graph Contrastive representation Learning method (LS-GCL) to model the structural information of nodes from multiple views. For the local view, the semantic subgraph of each target node is input into a shared GNN encoder to obtain the target node embeddings at the subgraph-level. For the global view, considering the original graph preserves indispensable semantic information of nodes, we leverage the shared GNN encoder to learn the target node embeddings at the global graph-level.
  arXiv  Detail & Related papers  (2023-08-07T03:23:46Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• Towards Explanation for Unsupervised Graph-Level Representation Learning [108.31036962735911]
  Existing explanation methods focus on the supervised settings, eg, node classification and graph classification, while the explanation for unsupervised graph-level representation learning is still unexplored. In this paper, we advance the Information Bottleneck principle (IB) to tackle the proposed explanation problem for unsupervised graph representations, which leads to a novel principle, textitUnsupervised Subgraph Information Bottleneck (USIB) We also theoretically analyze the connection between graph representations and explanatory subgraphs on the label space, which reveals that the robustness of representations benefit the fidelity of explanatory subgraphs.
  arXiv  Detail & Related papers  (2022-05-20T02:50:15Z)
• Parameterized Explainer for Graph Neural Network [49.79917262156429]
  We propose PGExplainer, a parameterized explainer for Graph Neural Networks (GNNs) Compared to the existing work, PGExplainer has better generalization ability and can be utilized in an inductive setting easily. Experiments on both synthetic and real-life datasets show highly competitive performance with up to 24.7% relative improvement in AUC on explaining graph classification.
  arXiv  Detail & Related papers  (2020-11-09T17:15:03Z)
• Hierarchical Message-Passing Graph Neural Networks [12.207978823927386]
  We propose a novel Hierarchical Message-passing Graph Neural Networks framework. Key idea is generating a hierarchical structure that re-organises all nodes in a flat graph into multi-level super graphs. We present the first model to implement this framework, termed Hierarchical Community-aware Graph Neural Network (HC-GNN)
  arXiv  Detail & Related papers  (2020-09-08T13:11:07Z)

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.