Towards Self-Explainable Graph Neural Network

1 INTRODUCTION

• GNN predictions are difficult to interpret because of their nonlinearity and reliance on both node attributes and graph topology; i.i.d.-focused explainers do not handle graph relations directly.Existing GNN explainers are post-hoc and may be biased or misrepresent the GNN’s true explanations.Source: §1 · p. 1
• Interpretable K-nearest labeled nodes can explain a prediction through neighbors’ labels and explain a match through similarities in local subgraphs.The paper illustrates this with a target node matched to a labeled positive node by local topology and node attributes.Source: §1 · p. 1
• The approach must combine node and structure similarity, identify neighbors without ground-truth similarity labels, and produce accurate predictions with corresponding explanations.Latent GNN representations can obscure which local attributes and structures support the neighbor selection.Source: §1 · p. 2
• SE-GNN explicitly models node and local-structure similarity, evaluates edge matches for structural explanations, and uses classification labels and contrastive learning to guide similarity modeling.Its classification loss is designed to support prediction accuracy and interpretable similarity modeling.Source: §1 · p. 2
• The paper introduces a synthetic dataset to quantitatively evaluate explanation quality and reports experiments on real-world and synthetic datasets.The stated contributions also include a framework for identifying interpretable K-nearest labeled nodes with self-supervision.Source: §1 · p. 2

2.1 Graph Neural Networks

• Spatial GNNs update node representations by aggregating neighbors, while spectral methods use graph spectral theory; GNN self-supervision has also used edge prediction and contrastive tasks.The cited examples include GCN, GAT, SuperGAT, and subgraph instance discrimination.Source: §2.1 · p. 2

2.2 Explainability of Graph Neural Networks

• Existing graph explainers use masks, local approximations, or feature importance, but GraphLime ignores graph structure and interpretable GNN work remains limited.The passage describes GNNExplainer, PGExplainer, and GraphLime as examples.Source: §2.2 · p. 2
• Unlike the cited post-hoc explainers, this work learns a self-explainable GNN that predicts and explains through K-nearest labeled nodes selected by node and structure similarity.The authors state that avoiding an additional explainer reduces the risk of misrepresenting the model’s decision reasons.Source: §2.2 · p. 2

3 PROBLEM DEFINITION

• In the semi-supervised setting, a graph has nodes, edges, and node attributes, with a subset of nodes labeled and the remainder unlabeled.Existing GNNs commonly predict labels for the unlabeled set, while self-explainable GNN research is described as limited.Source: §3 · p. 3
• For each unlabeled node, the target is to find K labeled nodes similar in both node features and centered n-hop subgraphs, then use them to predict and explain its label.The proposed explanation can cite the neighbors’ labels and the matching features and structures of their local subgraphs.Source: §3 · p. 3
• The formal task requires accurate predictions for unlabeled nodes and explanations consisting of the identified K nearest labeled nodes, their local subgraphs, and edge-matching results.The edge matches explain structural similarity between the target node’s local graph and each selected neighbor’s.Source: §3 · p. 3

4 METHODOLOGY

• For each node, SE-GNN identifies K similar labeled nodes and uses their labels for prediction while explaining the prediction through feature and structure similarity.The framework addresses the challenges of obtaining interpretable neighbors and jointly producing accurate predictions and correct explanations.Source: §4 · p. 3
• The framework combines an interpretable similarity module with a self-supervisor; a novel loss supports prediction accuracy and similarity modeling, while self-supervision further benefits explanation generation.The similarity process yields both the nearest labeled nodes and similarity explanations before prediction from those neighbors.Source: §4 · p. 3

4.1.1 Node Similarity.

• Node similarity uses MLP-encoded features followed by one residual GCN layer to update embeddings with neighbor information.The authors avoid direct comparison in raw feature space because features may be noisy and sparse, and note that deep GNNs can cause over-smoothing.Source: §4.1.1 · p. 3
• Node similarity is computed from learned embeddings using a flexible similarity function, such as cosine or distance-based similarity.The passage describes the embeddings as representations of the target and labeled nodes.Source: §4.1.1 · p. 3

4.1.2 Local Structure Similarity.

• Local structure similarity compares edges between the two nodes’ local graphs and uses matched edge pairs to explain their structural similarity.Edge representations aggregate their endpoint node information; the implementation uses average pooling.Source: §4.1.2 · p. 4

4.1.3 Overall Similarity.

• Overall similarity combines node and local structure similarity, with a positive scalar λ balancing their contributions.Source: §4.1.3 · p. 4

4.2 Self-Explainable Classification

• The target label is predicted as a weighted average of labels from the K nearest labeled nodes, with similarity-based weights controlled by temperature.The method identifies neighbors using the similarity metric described earlier.Source: §4.2 · p. 4

4.2.2 Explanation. 𝑡)}𝐾

• Explanations identify the nearest labeled nodes, contributions from node and structure similarity, and matched edge pairs between local graphs.The method can also filter unimportant edges from the target node’s local graph using a threshold.Source: §4.2.2 · pp. 4–5

4.2.3 Classification Loss.

• Training samples different-label nodes as negatives and same-label nodes as a support set for approximate K-nearest neighbors, maximizing same-label similarity and minimizing different-label similarity.This sampling strategy is used only during training; at test time, neighbors are identified from the whole labeled set.Source: §4.2.3 · p. 5

• Label-based supervision does not explicitly train node and local structure similarity, and unlabeled nodes are not involved in that objective.Source: §4.3 · p. 5
• Contrastive learning aligns node and edge representations across augmented graph views, using attribute masking and edge perturbation.Representations of the same node or edge across views form positive pairs; representations of different nodes form negative pairs.Source: §4.3 · p. 5
• The authors state that self-supervision can facilitate similarity modeling, while consistency across clean and edge-perturbed views leads to robustness against structure noise.Source: §4.3 · p. 5

• The final loss combines label-based prediction supervision with self-supervision on node similarity and edge matching.Hyperparameters α and β control the respective contributions of node-similarity and edge-matching self-supervision.Source: §4.4 · p. 5
• α controls self-supervision’s contribution to node similarity modeling.Source: §4.4 · p. 5
• β controls self-supervision’s contribution to edge matching in local similarity evaluation.Source: §4.4 · p. 5

4.5.1 Training Algorithm.

• Training computes classification loss, augments graphs, then calculates node- and edge-level contrastive losses.The algorithm uses attribute masking and edge perturbation to create graph views; negative-sample sizes are 20 for classification and 100 for each contrastive loss.Source: §4.5.1 · p. 6

4.5.2 Time Complexity.

• For a test node, similarity calculation across labeled nodes has approximate cost O(d·|E_t|·Σ_{v_l∈V_L}|E_l|).The edge-matching cost for each labeled node is O(d·|E_t|·|E_l|), where d is the embedding dimension.Source: §4.5.2 · p. 6
• Training samples positive and negative nodes to reduce the similarity pairs computed for classification loss.For each labeled node v_t, the sampled set is S_t = K_t ∪ V_t^n; the passage gives the per-node classification-loss cost as O(d·|E_t|·Σ_{v_l∈S_t}|E_l|).Source: §4.5.2 · p. 6
• An iteration’s training cost also includes node- and edge-level contrastive learning.The overall iteration complexity is expressed using the costs for node contrastive learning, edge contrastive learning, and sampled classification pairs.Source: §4.5.2 · p. 6

5.1 Datasets

• The evaluation uses three real-world benchmarks and two synthetic datasets; the synthetic datasets provide ground-truth explanations for quantitative analysis.Syn-Cora is derived from Cora and supplies ground-truth nearest labeled nodes and edge matches; BA-Shapes is built from a base Barabási–Albert graph with house motifs.Source: §5.1.2 · p. 6, §5.1 · p. 6

5.2.1 Baselines.

• The baselines include standard, self-supervised, and robust GNNs, K-nearest-neighbor variants, and post-hoc subgraph explainers.The real-world classification comparison includes GCN, GIN, SuperGAT, and Pro-GNN; explanation baselines include MLP-K, GCN-K, GIN-K, GNNExplainer, and PGExplainer.Source: §5.2.1 · pp. 6–7

5.2.2 Implementation Details.

• SE-GNN uses 2-hop local graphs for structure similarity, and its encoder has two MLP layers and one residual GCN layer with hidden dimension 64.The implementation also uses 0.2 attribute masking, perturbs 10% of edges, and sets the node/structure similarity balance λ to 0.5.Source: §5.2.2 · p. 7

5.3.1 Results on Real-World Datasets.

• SE-GNN outperforms GCN and GIN on real-world node classification, is comparable to SuperGAT, and performs better than GCN-K and GIN-K.The authors report five-run average accuracy and standard deviations; Table 2 presents node-classification accuracy on the real-world datasets.Source: §5.3.1 · p. 7, Table 2 · p. 7
• On real-world datasets, SE-GNN consistently outperforms baselines in precision@k for retrieving labeled nodes used for prediction and explanation.The evaluation varies k from 1 to 8; Figure 3 reports the precision@k results.Source: Figure 3 · p. 7, §5.3.1 · p. 8
• In human evaluation, SE-GNN’s identified nearest neighbors receive the highest average ratings among the compared methods.Thirty annotators rated explanations for at least 15 instances each across three real-world datasets; Table 3 reports average ratings.Source: §5.3.1 · p. 8, Table 3 · p. 8

5.3.3 Results on BA-Shapes.

• On BA-Shapes, SE-GNN achieves structure-explanation AUC comparable to state-of-the-art GNN explainers.The authors report average results from five runs in Table 5, although SE-GNN was not developed specifically for crucial-subgraph extraction.Source: §5.3.3 · p. 8, Table 5 · p. 8

5.4 Robustness

• At a 25% Metattack perturbation rate, SE-GNN improves over GCN by over 10% and outperforms Pro-GNN on Citeseer.The authors attribute robustness to contrastive learning across clean and perturbed graphs and low similarity scores for noisy edges.Source: §5.4 · p. 9, Figure 5 · p. 9

5.5 Ablation Study

• SE-GNN outperforms its 1-hop variant in prediction and explanation, and removing either self-supervision signal substantially reduces performance.The authors report these comparisons on Pubmed and Syn-Cora; Edge ACC on the 2-hop local graph is not applicable to the 1-hop variant.Source: §5.5 · p. 9, Figure 6 · p. 9

5.6 Parameter Sensitivity Analysis

• On Pubmed, α and β each show a rise-then-fall pattern, with values between 0.001 and 0.01 generally performing well.α weights self-supervision for node similarity, while β weights self-supervision for local-structure similarity.Source: §5.6 · p. 9, Figure 7 · p. 9

6 CONCLUSION AND FUTURE WORK

• SE-GNN finds K-nearest labeled nodes through interpretable similarity and uses them for label prediction and explanations.The framework also uses contrastive learning to benefit the similarity module.Source: §6 · p. 9
• Experiments on real-world and synthetic datasets demonstrate the framework’s effectiveness for explainable node classification.Source: §6 · p. 9
• The authors identify explainable link prediction and other pre-text tasks, including structural identity, as directions for further investigation.Source: §6 · p. 9