# Algorithmic Concept-based Explainable Reasoning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 54 references that are in the map.
- First posted on arXiv 15 Jul 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Concept Bottleneck Models](https://mlsanity.com/paper/2007.04612/) (2020)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [On Completeness-aware Concept-Based Explanations in Deep Neural Networks](https://mlsanity.com/paper/1910.07969/) (2019)
- [Concept Whitening for Interpretable Image Recognition](https://mlsanity.com/paper/2002.01650/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Now You See Me (CME): Concept-based Model Extraction](https://mlsanity.com/paper/2010.13233/) (2020)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [Neural Execution Engines: Learning to Execute Subroutines](https://mlsanity.com/paper/2006.08084/) (2020)
- [An Explicitly Relational Neural Network Architecture](https://mlsanity.com/paper/1905.10307/) (2019)
- [Neural Bipartite Matching](https://mlsanity.com/paper/2005.11304/) (2020)
- [XLVIN: eXecuted Latent Value Iteration Nets](https://mlsanity.com/paper/2010.13146/) (2020)
- [Is Disentanglement all you need? Comparing Concept-based & Disentanglement Approaches](https://mlsanity.com/paper/2104.06917/) (2021)
- [Persistent Message Passing](https://mlsanity.com/paper/2103.01043/) (2021)
- [MEME: Generating RNN Model Explanations via Model Extraction](https://mlsanity.com/paper/2012.06954/) (2020)
- [Failing Conceptually: Concept-Based Explanations of Dataset Shift](https://mlsanity.com/paper/2104.08952/) (2021)
- [PyTorch, Explain! A Python library for Logic Explained Networks](https://mlsanity.com/paper/2105.11697/) (2021)

## Built on by (most cited first, 12 of 12)

- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [Concept Activation Regions: A Generalized Framework For Concept-Based Explanations](https://mlsanity.com/paper/2209.11222/) (2022)
- [Interpretable Neural-Symbolic Concept Reasoning](https://mlsanity.com/paper/2304.14068/) (2023)
- [Global Concept-Based Interpretability for Graph Neural Networks via Neuron Analysis](https://mlsanity.com/paper/2208.10609/) (2022)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Parallel Algorithms Align with Neural Execution](https://mlsanity.com/paper/2307.04049/) (2023)
- [Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic](https://mlsanity.com/paper/2407.10820/) (2024)
- [Everybody Needs a Little HELP: Explaining Graphs via Hierarchical Concepts](https://mlsanity.com/paper/2311.15112/) (2023)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [GCI: A (G)raph (C)oncept (I)nterpretation Framework](https://mlsanity.com/paper/2302.04899/) (2023)

## Abstract (arXiv)

Recent research on graph neural network (GNN) models successfully applied GNNs to classical graph algorithms and combinatorial optimisation problems. This has numerous benefits, such as allowing applications of algorithms when preconditions are not satisfied, or reusing learned models when sufficient training data is not available or can't be generated. Unfortunately, a key hindrance of these approaches is their lack of explainability, since GNNs are black-box models that cannot be interpreted directly. In this work, we address this limitation by applying existing work on concept-based explanations to GNN models. We introduce concept-bottleneck GNNs, which rely on a modification to the GNN readout mechanism. Using three case studies we demonstrate that: (i) our proposed model is capable of accurately learning concepts and extracting propositional formulas based on the learned concepts for each target class; (ii) our concept-based GNN models achieve comparative performance with state-of-the-art models; (iii) we can derive global graph concepts, without explicitly providing any supervision on graph-level concepts.