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

Concept Graph Convolutions: Message Passing in the Concept Space
Apr 22, 2026Lucie Charlotte Magister, Pietro LioGraph Neural Networks Message Passing Neural Networks
University of Cambridge
Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning
Apr 13, 2026Xiaoxue Han, Libo Zhang, Zining Zhu +1GNN Explainability Text-Attributed Graph Learning
Department of Computer Science, Stevens Institute of Technology, Hoboken, NJ, USA.
Subgraph Concept Networks: Concept Levels in Graph Classification
Apr 20, 2026Lucie Charlotte Magister, Alexander Norcliffe, Iulia Duta +1Graph Neural Networks Hierarchical Representation Learning
University of Cambridge Cambridge, UK

Apr 22, 2026J/K move · Enter open · S save

Concept Graph Convolutions: Message Passing in the Concept Space

Lucie Charlotte Magister, Pietro Lio

University of Cambridge

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Concept Graph Convolutions: Message Passing in the Concept Space

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

Subgraph Concept Networks: Concept Levels in Graph Classification