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
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. ρ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. ρ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
Micro F1
Macro F1
μ AUPRC
MAUPRC
Fid+
Fid−
GT F1
GT IoU
SynAnchor
SEMGNN
0.915 ± 0.018
0.844 ± 0.043
0.946 ± 0.014
0.930 ± 0.024
0.860 ± 0.023
0.383 ± 0.017
0.463 ± 0.007
0.337 ± 0.006
w/o Pred-L
0.905 ± 0.032
0.823 ± 0.005
0.945 ± 0.022
0.916 ± 0.040
0.866 ± 0.006
0.359 ± 0.028
0.466 ± 0.023
0.338 ± 0.018
w/o Expl-L
0.910 ± 0.023
0.821 ± 0.021
0.945 ± 0.023
0.935 ± 0.028
0.879 ± 0.028
0.371 ± 0.008
0.456 ± 0.006
0.332 ± 0.005
Base
0.899 ± 0.023
0.814 ± 0.023
0.939 ± 0.019
0.919 ± 0.035
0.861 ± 0.012
0.354 ± 0.011
0.448 ± 0.026
0.325 ± 0.019
SynMotif
SEMGNN
0.903 ± 0.030
0.779 ± 0.053
0.900 ± 0.002
0.942 ± 0.004
0.878 ± 0.071
0.157 ± 0.016
0.320 ± 0.009
0.193 ± 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 ρ between training-label correlation and label-wise explanation overlap. A larger ρ indicates that more correlated labels tend to share more explanatory evidence. Δρ denotes the change from w/o Corr to w/ Corr. The HumLoc dataset has a negative Δρ because its labels are negatively correlated on average, meaning SEMGNN can adapt to label correlation (positive or negative) to find correlated evidence.
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.
Recent work has observed that explanations produced by Self-Interpretable Graph Neural Networks (SI-GNNs) can be self-inconsistent: when the model is reapplied to its own explanatory graph subset, it may produce a different explanation. However, why self-inconsistency arises remains poorly understood. In this work, we first identify re-explanation-induced context perturbation as the direct cause of score variation. We then introduce a latent signal assignment hypothesis to explain why only some edges are sensitive to this perturbation, and analyze how conciseness regularization affects latent signal assignment. Given that self-inconsistent edges do not provide stable evidence for the model's prediction, we propose Self-Denoising (SD), a model-agnostic and training-free post-processing strategy that calibrates explanations with only one additional forward pass. Experiments across representative SI-GNN frameworks, backbone architectures, and benchmark datasets support our hypothesis and show that SD consistently improves explanation quality while adding only about 4--6% computational overhead in practice.
Wenxin Tai, Yaqian Liu, Ting Zhong +1
University of Electronic Science and Technology of China
Graphs are a complex and versatile data structure used across various domains, with possibly multi-label nodes playing a particularly crucial role. Examples include proteins in PPI networks with multiple functions and users in social or e-commerce networks exhibiting diverse interests. Tackling multi-label node classification (MLNC) on graphs has led to the development of various approaches. Some methods leverage graph neural networks (GNNs) to exploit label co-occurrence correlations, while others incorporate label embeddings to capture label proximity. However, these approaches fail to account for the intricate influences between labels in non-Euclidean graph data. To address this issue, we decompose the message passing process in GNNs into two operations: propagation and transformation. We then conduct a comprehensive analysis and quantification of the influence correlations between labels in each operation. Building on these insights, we propose a novel model, Label Influence Propagation (LIP). Specifically, we construct a label influence graph based on the integrated label correlations. Then, we propagate high-order influences through this graph, dynamically adjusting the learning process by amplifying labels with positive contributions and mitigating those with negative influence. Finally, our framework is evaluated on comprehensive benchmark datasets, consistently outperforming SOTA methods across various settings, demonstrating its effectiveness on MLNC tasks.
Yifei Sun, Zemin Liu, Bryan Hooi +4
Zhejiang University · National University of Singapore · Capital One +1