Research map / Graph learning / GNN architectures
Higher Order Structures for Graph Explanations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FORGE, an explainer-agnostic framework that lifts graphs to restricted cell complexes, trains GNNs on them, and propagates cell-level explanations back to nodes to improve GNN explanation accuracy and faithfulness.
Problem
Existing GNN explainers operate on pairwise graph structure and struggle to capture higher-order, multi-node interactions, leading to less accurate explanations.
Approach
Lift the input graph to a restricted cell complex (vertices, edges, cycles as 2-cells) so that GNN training and any existing explainer operate on higher-order structure, then map the cell-level explanation mask back to the graph with information propagation algorithms (hierarchical, direct, entropy, activation).
Key results
- FORGE improves average explanation accuracy by 1.9x on real-world GraphXAI datasets and 2.25x on synthetic datasets (abstract).
- FORGE improves GEA up to 315% (FORGE-enhanced GradExplainer on Cube/Wheel), with the exception of Mutag for GNNExplainer.
- FORGE-enhanced explainers have comparable or lower (more faithful) GEF than base explainers on AlkaneCarbonyl, e.g. GradExplainer 0.389 to 0.078.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply FORGE to GNNExplainer | GNNExplainer · Benzene | GEA: 0.456 -> 0.772 | Helped |
| Apply FORGE to PGMExplainer | PGMExplainer · AlkCarb | GEA: 0.095 -> 0.304 | Helped |
| Apply FORGE to GNNExplainer | GNNExplainer · FluoCarb | GEA: 0.207 -> 0.441 | Helped |
| Apply FORGE to GNNExplainer | GNNExplainer · Mutag | GEA: 0.380 -> 0.339 | Hurt |
| Apply FORGE to SubgraphX | SubgraphX · Bull/Square | GEA: 0.355 -> 0.447 | Helped |
| Apply FORGE to SubgraphX | SubgraphX · House/Hex | GEA: 0.346 -> 0.617 | Helped |
| Apply FORGE to SubgraphX | SubgraphX · Wheel/House | GEA: 0.246 -> 0.549 | Helped |
| Apply FORGE to GradExplainer | GradExplainer · Cube/Wheel | GEA: 0.119 -> 0.494 | Helped |
| Apply FORGE to GNNExplainer | GNNExplainer · AlkaneCarbonyl | GEF: 0.189_{\pm 0.04} -> 0.083_{\pm 0.02} | Helped |
| Apply FORGE to GraphMask | GraphMask · AlkaneCarbonyl | GEF: 0.051_{\pm 0.03} -> 0.028_{\pm 0.02} | Helped |
| Apply FORGE to GradExplainer | GradExplainer · AlkaneCarbonyl | GEF: 0.389_{\pm 0.13} -> 0.078_{\pm 0.05} | Helped |
| Apply FORGE to PGMExplainer | PGMExplainer · AlkaneCarbonyl | GEF: 0.204_{\pm 0.05} -> 0.234_{\pm 0.03} | Hurt |
Surprising findings
- Some default explainers perform worse than the random baseline, but after applying FORGE all explainers surpass the random baseline.
- FORGE with PGMExplainer has higher (worse) GEF than the base explainer (0.234 vs 0.204).
Limitations
- Restricting boundary relations to drop higher-dimensional relations between p-cells (p>=1) is a simplification.
- Effect of information propagation varies across explainers and datasets; no single propagation method dominates.
- Mutag with GNNExplainer does not improve with FORGE.
Experimental setup
Datasets: GraphXAI Benzene GraphXAI Mutagenicity GraphXAI AlkylCarbonyl GraphXAI FluorideCarbonyl synthetic motif graphs (Bull, Square, Hexagon, Wheel, House, Cube)
Benchmarks: GraphXAI Benzene GraphXAI Mutagenicity GraphXAI AlkylCarbonyl GraphXAI FluorideCarbonyl synthetic Motif1/Motif2 datasets
Metrics: Graph Explanation Accuracy (GEA, Jaccard index) Graph Explanation Faithfulness (GEF, KL divergence)
Baselines: GNNExplainer GraphMask GradExplainer PGMExplainer SubgraphX Random explainer
Builds on: GNNExplainer SubgraphX GraphXAI cell complex neural networks
Closest papers by meaning
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.90)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.90)
- Explaining Graph Neural Networks via Structure-aware Interaction Index (ICML 2024 · similarity 0.90)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.89)
- Graph Segmentation and Contrastive Enhanced Explainer for Graph Neural Networks (AAAI 2025 · similarity 0.89)
- Factorized Explainer for Graph Neural Networks (AAAI 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.