Self-Explainable Multi-Label Graph Neural Network for Correlated Evidence Attribution

Yingqi Feng; Yufei Tang; Min Shi; Xingquan Zhu

cs.LGAug 27, 2026

Self-Explainable Multi-Label Graph Neural Network for Correlated Evidence Attribution

Authors: Yingqi Feng, Yufei Tang, Min Shi, Xingquan Zhu

Organizations: Department of Electrical Engineering and Computer Science, Florida Atlantic University, Boca Raton, FL, USA · School of Computing and Informatics, University of Louisiana at Lafayette, Lafayette, LA, USA

Abstract

Multi-label graph learning intends to capture the intrinsic complexity of real-world applications, where one sample is often related to multiple groups or consists of multiple objects. To date, a handful of multi-label graph learning methods exist, but none of them integrate training-time interpretation capability. While post-hoc graph explainers have been developed, they do not explicitly model label-dependent evidence sharing in multi-label graph learners, especially when label pairs are weakly or negatively associated. As a result, post-hoc approaches may miss how evidence should be shared or separated across different labels. This paper advances a new end-to-end self-explainable multi-label graph neural network (SEMGNN), which aims to simultaneously classify multi-labeled nodes and identify edges significantly contributing to each target node w.r.t. predicted labels. Different from post-hoc methods, SEMGNN jointly learns a predictor and a sparse edge-mask explainer within a unified framework and training objective. Label-label correlations are used to improve multi-label node classification and enhance individual label explanations, so that different labels of a node can be supported by distinct yet coherent structural and/or correlated evidence. Experiments and comparisons on synthetic and real-world multi-label networks, in social networking, entertainment, and life sciences, show that SEMGNN achieves competitive or improved predictive performance while providing more faithful and compact label-conditioned explanations.

Figures & tables

Fig. 1: Motivation of correlated evidence attribution in multi-label graph learning. From left to right: (a) a multi-label graph where each node is associated with multiple labels and some labels are more strongly correlated than others; (b) SEMGNN identifies important edges for multi-label prediction; and (c)–(d) label-conditioned explanations show that different labels of the same node may rely on distinct yet partially shared/correlated structural evidence.

Fig. 2: Overview of SEMGNN . Phase 1 jointly learns multi-label node classification and intrinsic edge masking with a shared prediction backbone and unified end-to-end objectives. Phase 2 answers a label-conditioned attribution query by producing a label-specific mask, fusing it with gradient-based necessity scores, and extracting a compact explanatory subgraph, accounting for correlated evidence attribution.

Dataset	$N$	$E$	$d$	$L$	Avg. Pair	Avg. Jac.	Avg. $\rho_{Y}$
SynAnchor	3,000	9,476	16	30	2.60	0.045	0.020
SynMotif	3,000	29,849	16	30	3.08	0.053	0.033
BlogCatalog	10,312	667,966	8	39	0.62	0.010	-0.009
YouTube	22,693	192,722	3	47	1.93	0.026	0.020
HumLoc	3,106	18,496	32	14	0.20	0.009	-0.044

TABLE I: Dataset statistics.

N

E

d

, and

L

denote the numbers of nodes, undirected edges, feature dimensions, and labels. Avg. Pair denotes the average number of within-node label pairs per node. Avg. Jac. and Avg.

\rho_{Y}

denote the average Jaccard similarity and Spearman correlation between binary label vectors over all label pairs, respectively.

Fig. 3: Visualization of multi-label explanations for a single node on SynAnchor.

Y

denotes the ground-truth label set of the target node, while labels=[...] denotes the predicted positive labels explained by each method. Green solid edges denote selected GT edges, i.e., true positives (TP); red dashed edges denote selected non-GT edges, i.e., false positives (FP); orange dashed edges denote GT edges missed by the explanation, i.e., false negatives (FN); and the orange star marks the target node. Each panel reports TP/FP/FN counts and Fid+/Fid- scores.

Fig. 4: Case studies of label-correlation-guided explanation sharing on SynAnchor (a) and YouTube (b). For each case, the top row shows label-wise explanations without label correlation (green edges), and the bottom row shows explanations with label correlation (orange edges). The center tables report pairwise label correlation and explanation overlap before and after enabling label correlation. In the SynAnchor case, structures shared by labels 17 and 25 are highlighted in red, while partially overlapping structures are marked with dashed circles. For the denser YouTube case, overlap changes are summarized in the center table for readability.

Dataset	Variant	Prediction				Explanation
Dataset	Variant	Micro F1	Macro F1	$\mu$ AUPRC	MAUPRC	$\mathrm{Fid}^{+}$	$\mathrm{Fid}^{-}$	GT F1	GT IoU
SynAnchor	SEMGNN	0.915 $\pm$ 0.018	0.844 $\pm$ 0.043	0.946 $\pm$ 0.014	0.930 $\pm$ 0.024	0.860 $\pm$ 0.023	0.383 $\pm$ 0.017	0.463 $\pm$ 0.007	0.337 $\pm$ 0.006
	w/o Pred-L	0.905 $\pm$ 0.032	0.823 $\pm$ 0.005	0.945 $\pm$ 0.022	0.916 $\pm$ 0.040	0.866 $\pm$ 0.006	0.359 $\pm$ 0.028	0.466 $\pm$ 0.023	0.338 $\pm$ 0.018
	w/o Expl-L	0.910 $\pm$ 0.023	0.821 $\pm$ 0.021	0.945 $\pm$ 0.023	0.935 $\pm$ 0.028	0.879 $\pm$ 0.028	0.371 $\pm$ 0.008	0.456 $\pm$ 0.006	0.332 $\pm$ 0.005
	Base	0.899 $\pm$ 0.023	0.814 $\pm$ 0.023	0.939 $\pm$ 0.019	0.919 $\pm$ 0.035	0.861 $\pm$ 0.012	0.354 $\pm$ 0.011	0.448 $\pm$ 0.026	0.325 $\pm$ 0.019
SynMotif	SEMGNN	0.903 $\pm$ 0.030	0.779 $\pm$ 0.053	0.900 $\pm$ 0.002	0.942 $\pm$ 0.004	0.878 $\pm$ 0.071	0.157 $\pm$ 0.016	0.320 $\pm$ 0.009	0.193 $\pm$ 0.006

TABLE IV: Ablation study on node prediction and explanation performance. Best results are in bold, and second-best results are underlined.

Fig. 5: Correlation–overlap alignment before and after enabling label-correlation modeling. The

y

-axis reports Spearman

\rho

between training-label correlation and label-wise explanation overlap. A larger

\rho

indicates that more correlated labels tend to share more explanatory evidence.

\Delta\rho

denotes the change from w/o Corr to w/ Corr. The HumLoc dataset has a negative

\Delta\rho

because its labels are negatively correlated on average, meaning SEMGNN can adapt to label correlation (positive or negative) to find correlated evidence.

GNN Explainability

Graph neural network explainability studies how to identify and communicate the features, nodes, edges, and subgraphs behind graph-model predictions.

See all 82 papers

MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing
May 13, 2026Chaokai Wu, Haofu Shi, Ningxuan Ma +2Multi-Label Classification Graph Neural Networks
Why Self-Inconsistency Arises in GNN Explanations and How to Exploit It
May 8, 2026Wenxin Tai, Yaqian Liu, Ting Zhong +1Explanation Stability GNN Explainability
University of Electronic Science and Technology of China
Multi-Label Node Classification with Label Influence Propagation
Jul 1, 2026Yifei Sun, Zemin Liu, Bryan Hooi +4Graph-Based Label Propagation Multi-Label Classification
Zhejiang University · National University of Singapore · Capital One +1

May 13, 2026J/K move · Enter open · S save

MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing

Chaokai Wu, Haofu Shi, Ningxuan Ma, Jianghong Ma+1

Multi-Label Classification Graph Neural Networks Over-Squashing in GNNs Information Bottleneck GNN Expressivity Message Passing Neural Networks

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) suffer from over-squashing in deep message passing, where information from exponentially growing neighborhoods is compressed into fixed-dimensional representations. We show that this issue becomes a distinct failure mode in multi-label graphs: neighboring nodes often share only limited labels while differing across many irrelevant ones, causing predictive signals to be diluted by noisy label information. To address this challenge, we propose the Multi-Label Graph Information Bottleneck (MLGIB), which formulates multi-label message passing as constrained information transmission under irrelevant label noise. MLGIB balances expressiveness and robustness by preserving predictive label signals while suppressing irrelevant noise. Specifically, it constructs a Markovian dependence space and derives tractable variational bounds, where the lower bound maximizes mutual information with target labels and the upper bound constrains redundant source information. These bounds lead to an end-to-end label-aware message-passing architecture. Extensive experiments on multiple benchmarks demonstrate consistent improvements over existing methods, validating the effectiveness and generality of the proposed framework.

Abstract

GNN Explainability

Explore similar work

MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing

Why Self-Inconsistency Arises in GNN Explanations and How to Exploit It

Multi-Label Node Classification with Label Influence Propagation