PaperlayerView exact revision on arXiv

Source-linked AI summary

XGNN: Towards Model-Level Explanations of Graph Neural Networks

Hao Yuan, Jiliang Tang, Xia Hu, Shuiwang Ji

arXiv:2006.02587v1cs.LGstat.ML

TL;DR

GNNs perform well on graph tasks but are often treated as black boxes, and prior graph interpretation work focuses on example-level explanations. XGNN trains a graph generator with reinforcement learning to produce valid graph patterns maximizing a target prediction, and experiments show these patterns help understand, verify, and potentially improve trained GNNs.

  • Problem

    GNNs achieve strong graph-task performance but lack human-intelligible, model-level explanations, while existing graph-model interpretation studies focus on individual examples.

  • Method

    XGNN trains a graph generator with reinforcement learning and policy-gradient feedback from a trained GNN to iteratively generate valid patterns maximizing a target prediction.

  • Results

    Experiments on synthetic and real-world datasets show that generated graphs consistently yield high predicted probabilities and expose patterns captured by trained GNNs.

  • Takeaways & Limitations

    Generated explanations help verify and understand trained GNNs and can guide retraining or improvement when model behavior conflicts with desired patterns.

  • Takeaways & Limitations

    The initial graph may be selected randomly or manually designed using prior domain knowledge, such as starting molecular generation from a carbon atom.

Abstract

from arXiv · show

Graphs neural networks (GNNs) learn node features by aggregating and combining neighbor information, which have achieved promising performance on many graph tasks. However, GNNs are mostly treated as black-boxes and lack human intelligible explanations. Thus, they cannot be fully trusted and used in certain application domains if GNN models cannot be explained. In this work, we propose a novel approach, known as XGNN, to interpret GNNs at the model-level. Our approach can provide high-level insights and generic understanding of how GNNs work. In particular, we propose to explain GNNs by training a graph generator so that the generated graph patterns maximize a certain prediction of the model.We formulate the graph generation as a reinforcement learning task, where for each step, the graph generator predicts how to add an edge into the current graph. The graph generator is trained via a policy gradient method based on information from the trained GNNs. In addition, we incorporate several graph rules to encourage the generated graphs to be valid. Experimental results on both synthetic and real-world datasets show that our proposed methods help understand and verify the trained GNNs. Furthermore, our experimental results indicate that the generated graphs can provide guidance on how to improve the trained GNNs.

1 INTRODUCTION

GNNs achieve strong performance across graph tasks but remain difficult to explain in human-intelligible terms. Existing interpretation approaches distinguish example-level explanations from more general model-level explanations, motivating XGNN for model-level GNN interpretation.

  • Motivation: GNNs have achieved state-of-the-art performance across node classification, graph classification, and link prediction, increasing their importance in real-world applications.Applications include social networks, chemistry, and biology.
  • Motivation: Despite strong performance, GNNs are commonly treated as black boxes and lack human-intelligible explanations.The passage identifies this as a limitation shared with other deep learning models.
  • Interpretation Types: Example-level interpretations explain individual predictions, whereas model-level interpretations provide more general and high-level explanations.The distinction concerns whether explanations target a given input or the model more broadly.
  • Interpretation Types: Checking many example-level explanations to verify a model can be time-consuming and require extensive expert effort.Model-level explanations require less human supervision because they are more general and high-level.
  • XGNN: XGNN addresses the lack of model-level GNN interpretation by generating graph patterns that maximize a target prediction.It trains a graph generator with reinforcement learning, policy-gradient feedback from trained GNNs, and graph rules encouraging valid outputs.

2 RELATED WORK

Graph models use feature and adjacency matrices, while graph-specific model-level interpretation remains challenging. Prior methods include input optimization for images and example-level graph explanations, motivating XGNN's graph-generation approach.

  • Graph Models: A graph G with n nodes is represented by a feature matrix X ∈ R^n×d and an adjacency matrix A ∈ {0, 1}^n×n.Each node has a d-dimensional feature vector.
  • Graph Models: Graph convolution layers aggregate j-hop neighborhood information by stacking j layers.The described operator adds self-loops, normalizes adjacency information, applies trainable linear transformations, and uses nonlinear activation.
  • Model-Level Interpretations: Input optimization generates inputs that maximize a deep model behavior while keeping network parameters fixed and treating the input as trainable.These methods are established for image and text models.
  • Model-Level Interpretations: Input optimization cannot directly interpret GNNs because graph structure uses a discrete adjacency matrix that is not directly optimized by back-propagation.The passage also notes that abstract optimized graphs lack the direct visual semantics available for images.
  • Graph Interpretations: Existing graph interpretation studies primarily provide input-dependent, example-level explanations, requiring potentially infeasible inspection across examples.GNN Explainer uses soft masks over graph edges and node features for a given example.
  • Graph Interpretations: XGNN proposes graph generation to provide higher-level, general model-level interpretations for GNNs.The generated graphs are designed to maximize a specified model behavior.

3 XGNN: EXPLAINABLE GRAPH NEURAL NETWORKS

XGNN explains graph neural networks at the model level by generating graph patterns that maximize a chosen class prediction. It uses reinforcement learning, trained-model feedback, and graph-validity rules to produce interpretable patterns for graph classification.

  • 3.1 Model-Level GNN Interpretation: XGNN identifies graph or subgraph patterns that maximize a trained GNN's predicted probability for a chosen class.These optimized patterns serve as model-level interpretations for that class.
  • 3.1 Model-Level GNN Interpretation: Unlike manual inspection of large datasets, XGNN trains a graph generator to produce smaller, less complex graphs for analysis.Graph rules such as chemical valency checks encourage valid and human-intelligible explanations.
  • 3.2 Interpreting GNNs via Graph Generation: The generator constructs an optimized graph step by step, adding edges between existing nodes or connecting candidate node types to the current graph.The current partial graph is the reinforcement-learning state, and each action selects an edge's starting and ending nodes.
  • 3.2 Interpreting GNNs via Graph Generation: A graph-neural-network policy predicts action probabilities from the partial graph and candidate set, and policy gradients train the generator.Generation can begin from a random candidate node or a manually designed initial graph, with maximum steps and nodes controlling termination.
  • 3.4 Training the Graph Generator: The reward combines trained-GNN feedback favoring high scores for the target class with graph-rule feedback favoring valid structures.Intermediate and overall rewards are used; final-graph rewards can average evaluations from multiple rollouts.
  • 3.2 Interpreting GNNs via Graph Generation: XGNN is presented as a general model-level interpretation framework whose graph-generation component can use methods suited to the dataset and GNN.The framework is formulated as reinforcement learning because generating a new graph is non-differentiable.

4 EXPERIMENTAL STUDIES

XGNN is evaluated on a synthetic dataset with known structural explanations and on MUTAG, where explanations probe graph structures and atom labels. The generated patterns consistently achieve high target probabilities, expose learned cues, and indicate limitations that can guide model improvement.

  • Dataset and Experimental Setup: XGNN is evaluated on Is_Acyclic, which labels graphs as cyclic or acyclic, and on MUTAG, whose chemical graphs encode atom types and mutagenic effects.The experiments assess structural explanations with available ground truth and explanations involving both graph structure and node labels.
  • Experimental Results on Synthetic Data: On Is_Acyclic, generated explanations for the cyclic class contain circles, whereas acyclic explanations contain no circles across different maximum node limits.The synthetic dataset provides ground-truth structure for checking whether the classifier distinguishes classes through circularity.
  • Experimental Results on Synthetic Data: The generated synthetic graphs consistently yield high predicted probabilities for their corresponding classes, including p = 0.7544 for the three-node cyclic explanation.The three-node cyclic graph has the highest probability among all possible graphs with three nodes.
  • Experimental Results on Synthetic Data: XGNN's synthetic explanations suggest that the trained classifier distinguishes classes by detecting circular structures, consistent with the dataset's labeling rule.The generated graphs are smaller and simpler than dataset graphs, which average 28 nodes and 30 edges, while yielding higher predicted probabilities.
  • Experimental Results on Real-World Data: On MUTAG, mutagenic explanations commonly contain carbon rings and NO2 groups, while non-mutagenic explanations frequently contain Chlorine or Chlorine-Bromine-Fluorine combinations.All graphs in Figure 4 start from a single Carbon atom, and atom colors identify different atom types.
  • Experimental Results on Real-World Data: Changing the initial graph still lets XGNN find mutagenic patterns, but Chlorine-containing graphs can receive mutagenic predictions, revealing limitations in the trained GNNs.The authors suggest emphasizing Chlorine graphs during training or using generated explanations for retraining and improvement.

5 CONCLUSIONS

XGNN addresses the lack of model-level interpretations for graph neural networks by generating graph patterns that maximize selected predictions. Experiments on synthetic and real-world datasets show that these explanations help verify and understand trained GNNs and can guide improvement.

  • Conclusions: XGNN targets the underexplored problem of model-level interpretation for graph models, beyond existing example-level explanations.The paper frames model-level explanations as more general and high-level than example-level analyses.
  • Conclusions: XGNN trains a graph generator with reinforcement learning to iteratively add edges that produce graph patterns maximizing a selected GNN prediction.Graph rules are incorporated to encourage valid and human-intelligible generated graphs.
  • Conclusions: Experiments show that generated graphs reveal patterns associated with high predictions and help verify and better understand trained GNN models.The evaluations cover both synthetic and real-world datasets.
  • Conclusions: Generated explanations can guide GNN improvement by identifying graphs that the trained model handles contrary to desired patterns and suggesting targeted retraining.The paper gives increased emphasis on Chlorine-containing graphs as one example of this guidance.
Loading 2006.02587v1…