Revealing Combinatorial Reasoning of GNNs via Graph Concept Bottleneck Layer

Yue Niu; Zhaokai Sun; Jiayi Yang; Xiaofeng Cao; Rui Fan; Xin Sun; Hanli Wang; Wei Ye

cs.LGMar 2, 2026

Revealing Combinatorial Reasoning of GNNs via Graph Concept Bottleneck Layer

Authors: Yue Niu, Zhaokai Sun, Jiayi Yang, Xiaofeng Cao, Rui Fan, Xin Sun, Hanli Wang, Wei Ye

Organizations: Tongji University, Shanghai, China · City University of Macau, Macau, China

Abstract

Despite their success in various domains, the growing dependence on GNNs raises a critical concern about the nature of the combinatorial reasoning underlying their predictions, which is often hidden within their black-box architectures. Addressing this challenge requires understanding how GNNs translate topological patterns into logical rules. However, current works only uncover the hard logical rules over graph concepts, which cannot quantify the contribution of each concept to prediction. Moreover, they are post-hoc interpretable methods that generate explanations after model training and may not accurately reflect the true combinatorial reasoning of GNNs, since they approximate it with a surrogate. In this work, we develop a graph concept bottleneck layer that can be integrated into any GNN architectures to guide them to predict the selected discriminative global graph concepts. The predicted concept scores are further projected to class labels by a sparse linear layer. It enforces the combinatorial reasoning of GNNs' predictions to fit the soft logical rule over graph concepts and thus can quantify the contribution of each concept. To further improve the quality of the concept bottleneck, we treat concepts as "graph words" and graphs as "graph sentences", and leverage language models to learn graph concept embeddings. Extensive experiments on multiple datasets show that our method GCBMs achieve state-of-the-art performance both in classification and interpretability.

Figures & tables

Figure 1: Overview of the GCBMs construction pipeline.

Figure 2: On the left side is a graph, and on the right side is its WL-subtree of height 2 rooted at the node with label 1.

Figure 3: Distributions of the WL-subtrees ( $\text{height}\leq 2$ ) in graph datasets MUTAG, COX2, BZR, and DHFR. The $x$ -axis denotes WL-subtree rank (i.e., the number of occurrences of a WL-subtree), and the $y$ -axis denotes the number of WL-subtrees with the same rank. These distributions approximate a power law.

	Dataset	MUTAG	PTC-MR	BZR	COX2	DHFR	PROTEINS	IMDB-B	IMDB-M	COLLAB	DBLP_v1
Group 1	GNNExplainer	66.5 $\pm$ 2.3	67.1 $\pm$ 6.2	81.1 $\pm$ 10.4	80.7 $\pm$ 6.6	69.8 $\pm$ 7.2	71.9 $\pm$ 4.9	70.4 $\pm$ 4.2	45.0 $\pm$ 4.3	77.6 $\pm$ 5.0	82.8 $\pm$ 0.4
	PGExplainer	78.6 $\pm$ 11.4	67.0 $\pm$ 5.5	82.9 $\pm$ 2.7	72.2 $\pm$ 2.7	69.0 $\pm$ 6.4	72.5 $\pm$ 3.5	62.2 $\pm$ 4.0	40.0 $\pm$ 6.5	75.7 $\pm$ 4.5	81.2 $\pm$ 0.5
	ProtGNN	77.6 $\pm$ 4.7	68.2 $\pm$ 5.8	82.5 $\pm$ 2.5	79.2 $\pm$ 3.1	70.8 $\pm$ 2.3	74.3 $\pm$ 2.6	58.3 $\pm$ 7.3	36.0 $\pm$ 5.7	69.3 $\pm$ 8.6	80.0 $\pm$ 0.6
	VGIB	72.1 $\pm$ 21.6	66.5 $\pm$ 6.1	79.8 $\pm$ 3.9	80.0 $\pm$ 4.2	51.7 $\pm$ 10.5	68.4 $\pm$ 6.5	50.8 $\pm$ 3.7	33.9 $\pm$ 3.1	72.3 $\pm$ 4.8	80.5 $\pm$ 0.8
	PGIB	76.6 $\pm$ 6.8	66.9 $\pm$ 5.4	83.7 $\pm$ 5.8	75.8 $\pm$ 2.3	77.4 $\pm$ 4.1	74.7 $\pm$ 3.1	57.0 $\pm$ 2.9	37.0 $\pm$ 3.9	73.2 $\pm$ 4.9	81.3 $\pm$ 0.7
	ConfExplainer	82.5 $\pm$ 6.7	66.8 $\pm$ 6.1	83.1 $\pm$ 5.2	75.5 $\pm$ 3.8	71.8 $\pm$ 8.2	72.5 $\pm$ 5.2	65.6 $\pm$ 5.4	44.9 $\pm$ 4.5	77.5 $\pm$ 5.2	82.7 $\pm$ 0.6

Table 1: Classification accuracy (mean%

\pm

standard deviation%) of GCBMs and baseline models of 10-fold cross-validation on benchmark datasets. The best results are in bold and the second-best results are as underlined (This notation applies to all subsequent tables).

Dataset	PC-3	MCF-7
GNNExplainer	84.1 $\pm$ 1.6	79.7 $\pm$ 1.5
ConfExplainer	83.7 $\pm$ 1.5	79.2 $\pm$ 1.4
GIN	84.6 $\pm$ 1.4	80.6 $\pm$ 1.5
GRDL	85.1 $\pm$ 1.6	81.4 $\pm$ 1.3
GCBM-E	88.8 $\pm$ 1.7	86.2 $\pm$ 1.3

Table 2: AUC scores (mean%

\pm

standard deviation%) of 10-fold cross-validation of each method on class-imbalanced benchmark datasets (only results of methods that can complete the experiments in 24 hours are reported).

Figure 4: The sankey diagram of the classification layer weights of GCBM on the DHFR dataset. The width of the connection between each concept and class corresponds to the exponent of the absolute value of the learned concept weight. To highlight core concepts, only the top 8 concepts with the largest absolute values of weights in each class are shown.

Figure 5: Concept indices and their corresponding specific functional groups in molecules from the DHFR dataset.

Figure 6: Key graph concepts and sample molecules with these concepts from each class in the DHFR dataset. The red part indicates the target substructure that each key concept is mapped back to in the original graph.

Dataset	Solubility	Benzene
GNNExplainer	51.8	54.7
PGExplainer	77.9	48.2
ProtGNN	56.2	66.4
VGIB	67.5	62.2
PGIB	65.0	61.3
ConfExplainer	80.5	75.3

Table 3: AUC scores (mean%) of each method on datasets Solubility and Benzene for interpretability evaluation. The selected two concepts are shared for GCBM and GCBM-E, leading to the same results.

Dataset	MUTAG	COX2	DHFR	IMDB-M
GCBM- $\mathcal{V}$	92.5 $\pm$ 4.3	85.0 $\pm$ 2.5	85.7 $\pm$ 3.3	53.0 $\pm$ 3.3
GCBM-GCN	87.7 $\pm$ 6.2	85.0 $\pm$ 3.4	84.2 $\pm$ 2.4	52.2 $\pm$ 3.4
GCBM-G	93.0 $\pm$ 4.2	85.7 $\pm$ 2.9	86.0 $\pm$ 3.7	52.4 $\pm$ 2.1
GCBM-E	93.6 $\pm$ 4.0	85.9 $\pm$ 3.2	86.1 $\pm$ 3.2	53.1 $\pm$ 2.4

Table 4: Classification accuracy (mean%

\pm

standard deviation%) of GCBM-E and its variants on benchmark datasets. GCBM-

\mathcal{V}

adopts a randomly selected concept set; GCBM-GCN replaces the backbone GIN with GCN; GCBM-G replaces Transformer with GloVe.

Figure 7: Parameter sensitivity analysis of GCBM-E: $\lambda_{c}$ (graph concept loss weight), $K$ (the maximum height of the WL-subtrees), and $\lambda_{r}$ (sparse regularization weight).

Model	Intervention Target	$W_{F[\text{cls 0},\text{cpt j}]}$	$W_{F[\text{cls 1},\text{cpt j}]}$	Impact	Accuracy
GCBM	$\hat{\mathbf{c}}_{i}$ of misclassified samples	NMR	NMR	+12 corrections	85.7 $\to$ 87.3
GCBM-E	$W_{F[\text{cls 0},\text{cpt 20}]}$ , $W_{F[\text{cls 1},\text{cpt 20}]}$	0.384 $\to$ -0.037	-0.011 $\to$ 0.410	+11 corrections; +6 new errors	86.1 $\to$ 86.8
GCBM-E	$W_{F[\text{cls 0},\text{cpt 42}]}$ , $W_{F[\text{cls 1},\text{cpt 42}]}$	0.188 $\to$ -0.247	0.094 $\to$ 0.528	+8 corrections; +5 new errors	86.1 $\to$ 86.5
GCBM-E	$W_{F[\text{cls 0},\text{cpt 20/42}]}$ , $W_{F[\text{cls 1},\text{cpt 20/42}]}$	0.384/0.188 $\to$ -0.037/-0.247	-0.011/0.094 $\to$ 0.410/0.528	+15 corrections; +8 new errors	86.1 $\to$ 87.0

Table 5: Intervention results of GCBM and GCBM-E on the DHFR dataset.

W_{F[\text{cls},\text{cpt}]}

denotes the weight of the target concept (cpt) corresponding to the class (cls) in the final classification layer weight matrix

W_{F}

. NMR indicates no modification required. Accuracy represents the classification accuracy (mean%) before and after intervention.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Component	MUTAG	COX2	DHFR	IMDB-M	COLLAB
WL-subtree extraction	4.43	4.97	6.49	7.54	16840.92
Information gain computation	0.68	1.20	1.24	1.19	2435.85
Transformer training	7.27	10.53	15.59	22.11	39720.67

Appendix

Table 6: Preprocessing time (in seconds) of each component in GCBM-E .

Dataset	MUTAG	COX2	DHFR	IMDB-M	COLLAB
GNNExplainer	388.22	677.19	771.87	2058.63	122602.41
WWL	4.75	44.52	117.29	263.62	10044.34
GIN	392.35	726.21	981.19	2452.42	126747.07
GRDL	195.76	356.20	541.52	1438.94	107040.14
GCBM	177.60	337.38	476.58	1353.61	96191.98
GCBM-E	198.93	388.93	577.29	1521.60	106338.83

Appendix

Table 7: Training time (in seconds) of GCBMs and representative baselines.

Dataset	Solubility	Benzene
$M_{I}$ =2	91.2	83.6
$M_{I}$ =5	81.2	85.9
$M_{I}$ =10	72.8	86.1
$M_{I}$ =15	68.9	84.0

Appendix

Table 8: AUC scores (mean%) of GCBM/GCBM-E with different

M_{I}

values.

Concept	$\overline{\Delta a}$	$\overline{f^{(j)}}$	$\Delta w$	$W_{F[\text{cls 0},\text{cpt j}]}$	$W_{F[\text{cls 1},\text{cpt j}]}$
cpt 20	0.51	0.8426	0.4213	0.3842 $\to$ -0.0371	-0.0112 $\to$ 0.4101
cpt 42	0.32	0.7635	0.3405	0.1876 $\to$ -0.2466	0.0939 $\to$ 0.5281

Appendix

Table 9: Detailed parameters of the intervention experiments.

Explore similar work

Apr 22, 2026

Concept Graph Convolutions: Message Passing in the Concept Space

The trust in the predictions of Graph Neural Networks is limited by their opaque reasoning process. Prior methods have tried to explain graph networks via concept-based explanations extracted from the latent representations obtained after message passing. However, these explanations fall short of explaining the message passing process itself. To this aim, we propose the Concept Graph Convolution, the first graph convolution designed to operate on node-level concepts for improved interpretability. The proposed convolutional layer performs message passing on a combination of raw and concept representations using structural and attention-based edge weights. We also propose a pure variant of the convolution, only operating in the concept space. Our results show that the Concept Graph Convolution allows to obtain competitive task accuracy, while enabling an increased insight into the evolution of concepts across convolutional steps.

Lucie Charlotte Magister, Pietro Lio

University of Cambridge

Graph Neural Networks Message Passing Neural Networks Concept-Based Explanations GNN Explainability

Ask PDF

Apr 13, 2026

Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning

We introduce Graph Concept Bottleneck (GCB) as a new paradigm for self-explainable text-attributed graph learning. GCB maps graphs into a subspace, concept bottleneck, where each concept is a meaningful phrase, and predictions are made based on the activation of these concepts. Unlike existing interpretable graph learning methods that primarily rely on subgraphs as explanations, the concept bottleneck provides a new form of interpretation. To refine the concept space, we apply the information bottleneck principle to focus on the most relevant concepts. This not only yields more concise and faithful explanations but also explicitly guides the model to "think" toward the correct decision. We empirically show that GCB achieves intrinsic interpretability with accuracy on par with black-box Graph Neural Networks. Moreover, it delivers better performance under distribution shifts and data perturbations, showing improved robustness and generalizability, benefitting from concept-guided prediction.

Xiaoxue Han, Libo Zhang, Zining Zhu +1

Department of Computer Science, Stevens Institute of Technology, Hoboken, NJ, USA.

GNN Explainability Text-Attributed Graph Learning Concept Bottleneck Models

Ask PDF

Apr 20, 2026

Subgraph Concept Networks: Concept Levels in Graph Classification

The reasoning process of Graph Neural Networks is complex and considered opaque, limiting trust in their predictions. To alleviate this issue, prior work has proposed concept-based explanations, extracted from clusters in the model's node embeddings. However, a limitation of concept-based explanations is that they only explain the node embedding space and are obscured by pooling in graph classification. To mitigate this issue and provide a deeper level of understanding, we propose the Subgraph Concept Network. The Subgraph Concept Network is the first graph neural network architecture that distils subgraph and graph-level concepts. It achieves this by performing soft clustering on node concept embeddings to derive subgraph and graph-level concepts. Our results show that the Subgraph Concept Network allows to obtain competitive model accuracy, while discovering meaningful concepts at different levels of the network.

Lucie Charlotte Magister, Alexander Norcliffe, Iulia Duta +1

University of Cambridge Cambridge, UK

Graph Neural Networks Hierarchical Representation Learning Concept-Based Explanations Graph Classification GNN Explainability

Ask PDF