Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods

Chirag Agarwal, M. Zitnik, Himabindu Lakkaraju

Main figure for Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods

Abstract

As Graph Neural Networks (GNNs) are increasingly being employed in critical real-world applications, several methods have been proposed in recent literature to explain the predictions of these models. However, there has been little to no work on systematically analyzing the reliability of these methods. Here, we introduce the first-ever theoretical analysis of the reliability of state-of-the-art GNN explanation methods. More specifically, we theoretically analyze the behavior of various state-of-the-art GNN explanation methods with respect to several desirable properties (e.g., faithfulness, stability, and fairness preservation) and establish upper bounds on the violation of these properties. We also empirically validate our theoretical results using extensive experimentation with nine real-world graph datasets. Our empirical results further shed light on several interesting insights about the behavior of state-of-the-art GNN explanation methods.

Benchmark Results

Tested on 5 datasets Non-standard metric on 5 datasets

Tables show presented results in global context (best 3 papers + GCN + MLP).

Classic

CiteSeer

Global leaderboard →

Default metric is Accuracy. The paper reports 0 values on Accuracy , 9 values on Unfaithfulness and 9 values on Instability .

Sorted by Unfaithfulness. Highlighted rows are from other papers.

#	Model	Accuracy ↓ default	Unfaithfulness ↓	Instability ↓	Paper
1	GraphLIME Trad baseline	—	0.0010 ± 0.0000	0.0480 ± 0.0150	Accuracy — Instability 0.0480 ± 0.0150 This paper
2	Random Node Features Trad baseline	—	0.0030 ± 0.0000	0.1800 ± 0.0000	Accuracy — Instability 0.1800 ± 0.0000 This paper
3	VanillaGrad Hyb baseline	—	0.0030 ± 0.0000	0.1420 ± 0.0020	Accuracy — Instability 0.1420 ± 0.0020 This paper
4	GNNExplainer GNN baseline	—	0.0030 ± 0.0000	0.2120 ± 0.0150	Accuracy — Instability 0.2120 ± 0.0150 This paper
5	Integrated Gradients GNN baseline	—	0.0040 ± 0.0000	0.8960 ± 0.0000	Accuracy — Instability 0.8960 ± 0.0000 This paper
6	Random Edges Trad baseline	—	0.0050 ± 0.0000	0.2630 ± 0.0190	Accuracy — Instability 0.2630 ± 0.0190 This paper
7	PGMExplainer GNN baseline	—	0.0090 ± 0.0010	0.2620 ± 0.0150	Accuracy — Instability 0.2620 ± 0.0150 This paper
8	PGExplainer GNN baseline	—	0.1290 ± 0.0100	0.4000 ± 0.0170	Accuracy — Instability 0.4000 ± 0.0170 This paper
9	GraphMask GNN baseline	—	0.1700 ± 0.0070	0.2000 ± 0.0280	Accuracy — Instability 0.2000 ± 0.0280 This paper

PubMed

Global leaderboard →

Default metric is Accuracy. The paper reports 0 values on Accuracy , 9 values on Unfaithfulness and 9 values on Instability .

Sorted by Unfaithfulness. Highlighted rows are from other papers.

#	Model	Accuracy ↓ default	Unfaithfulness ↓	Instability ↓	Paper
1	GraphLIME Trad baseline	—	0.0010 ± 0.0010	0.4400 ± 0.0230	Accuracy — Instability 0.4400 ± 0.0230 This paper
2	Random Node Features Trad baseline	—	0.0020 ± 0.0000	0.1800 ± 0.0000	Accuracy — Instability 0.1800 ± 0.0000 This paper
3	Random Edges Trad baseline	—	0.0020 ± 0.0000	0.1950 ± 0.0020	Accuracy — Instability 0.1950 ± 0.0020 This paper
4	GNNExplainer GNN baseline	—	0.0020 ± 0.0000	0.1920 ± 0.0020	Accuracy — Instability 0.1920 ± 0.0020 This paper
5	VanillaGrad Hyb baseline	—	0.0030 ± 0.0000	0.1390 ± 0.0020	Accuracy — Instability 0.1390 ± 0.0020 This paper
6	Integrated Gradients GNN baseline	—	0.0040 ± 0.0000	0.8550 ± 0.0030	Accuracy — Instability 0.8550 ± 0.0030 This paper
7	GraphMask GNN baseline	—	0.0100 ± 0.0020	0.7420 ± 0.0180	Accuracy — Instability 0.7420 ± 0.0180 This paper
8	PGMExplainer GNN baseline	—	0.0450 ± 0.0030	0.1420 ± 0.0080	Accuracy — Instability 0.1420 ± 0.0080 This paper
9	PGExplainer GNN baseline	—	0.0940 ± 0.0040	0.3670 ± 0.0060	Accuracy — Instability 0.3670 ± 0.0060 This paper

TU Dortmund

MUTAG

Global leaderboard →

Default metric is Accuracy. The paper reports 0 values on Accuracy , 6 values on Unfaithfulness and 6 values on Instability .

Sorted by Unfaithfulness. Highlighted rows are from other papers.

#	Model	Accuracy ↓ default	Unfaithfulness ↓	Instability ↓	Paper
1	Random Edges Trad baseline	—	0.0220 ± 0.0290	0.3660 ± 0.0640	Accuracy — Instability 0.3660 ± 0.0640 This paper
2	Integrated Gradients GNN baseline	—	0.0860 ± 0.0460	0.4730 ± 0.0870	Accuracy — Instability 0.4730 ± 0.0870 This paper
3	GNNExplainer GNN baseline	—	0.0940 ± 0.0520	0.4900 ± 0.0460	Accuracy — Instability 0.4900 ± 0.0460 This paper
4	Random Node Features Trad baseline	—	0.1050 ± 0.0560	0.4920 ± 0.0460	Accuracy — Instability 0.4920 ± 0.0460 This paper
5	PGMExplainer GNN baseline	—	0.1540 ± 0.0830	0.3850 ± 0.1180	Accuracy — Instability 0.3850 ± 0.1180 This paper
6	VanillaGrad Hyb baseline	—	0.2950 ± 0.0780	0.3630 ± 0.1290	Accuracy — Instability 0.3630 ± 0.1290 This paper

OGB

ogbn-arxiv

Global leaderboard →

Default metric is Accuracy. The paper reports 0 values on Accuracy , 9 values on Unfaithfulness and 9 values on Instability .

Sorted by Unfaithfulness. Highlighted rows are from other papers.

#	Model	Accuracy ↓ default	Unfaithfulness ↓	Instability ↓	Paper
1	GraphLIME Trad baseline	—	0.2600 ± 0.0030	0.3740 ± 0.0040	Accuracy — Instability 0.3740 ± 0.0040 This paper
2	PGExplainer GNN baseline	—	0.3380 ± 0.0020	0.3810 ± 0.0010	Accuracy — Instability 0.3810 ± 0.0010 This paper
3	PGMExplainer GNN baseline	—	0.4130 ± 0.0020	0.2700 ± 0.0020	Accuracy — Instability 0.2700 ± 0.0020 This paper
4	GNNExplainer GNN baseline	—	0.4300 ± 0.0020	0.3760 ± 0.0010	Accuracy — Instability 0.3760 ± 0.0010 This paper
5	Random Edges Trad baseline	—	0.4310 ± 0.0020	0.3780 ± 0.0010	Accuracy — Instability 0.3780 ± 0.0010 This paper
6	VanillaGrad Hyb baseline	—	0.5280 ± 0.0020	0.3590 ± 0.0010	Accuracy — Instability 0.3590 ± 0.0010 This paper
7	Integrated Gradients GNN baseline	—	0.5280 ± 0.0020	0.3720 ± 0.0000	Accuracy — Instability 0.3720 ± 0.0000 This paper
8	Random Node Features Trad baseline	—	0.5290 ± 0.0020	0.3750 ± 0.0000	Accuracy — Instability 0.3750 ± 0.0000 This paper
9	GraphMask GNN baseline	—	0.5860 ± 0.0010	0.1250 ± 0.0020	Accuracy — Instability 0.1250 ± 0.0020 This paper

ogbn-mag

Global leaderboard →

Default metric is Accuracy. The paper reports 0 values on Accuracy , 9 values on Unfaithfulness and 9 values on Instability .

Sorted by Unfaithfulness. Highlighted rows are from other papers.

#	Model	Accuracy ↓ default	Unfaithfulness ↓	Instability ↓	Paper
1	GraphLIME Trad baseline	—	0.0010 ± 0.0000	0.3540 ± 0.0230	Accuracy — Instability 0.3540 ± 0.0230 This paper
2	Random Node Features Trad baseline	—	0.0020 ± 0.0000	0.3730 ± 0.0020	Accuracy — Instability 0.3730 ± 0.0020 This paper
3	Random Edges Trad baseline	—	0.0020 ± 0.0000	0.3760 ± 0.0020	Accuracy — Instability 0.3760 ± 0.0020 This paper
4	VanillaGrad Hyb baseline	—	0.0020 ± 0.0000	0.3120 ± 0.0050	Accuracy — Instability 0.3120 ± 0.0050 This paper
5	Integrated Gradients GNN baseline	—	0.0020 ± 0.0000	0.3680 ± 0.0020	Accuracy — Instability 0.3680 ± 0.0020 This paper
6	PGMExplainer GNN baseline	—	0.0020 ± 0.0000	0.2220 ± 0.0060	Accuracy — Instability 0.2220 ± 0.0060 This paper
7	GraphMask GNN baseline	—	0.0020 ± 0.0000	0.3230 ± 0.0030	Accuracy — Instability 0.3230 ± 0.0030 This paper
8	GNNExplainer GNN baseline	—	0.0020 ± 0.0000	0.3750 ± 0.0020	Accuracy — Instability 0.3750 ± 0.0020 This paper
9	PGExplainer GNN baseline	—	0.0020 ± 0.0000	0.3750 ± 0.0060	Accuracy — Instability 0.3750 ± 0.0060 This paper

SOTA performance (not significantly different from the best) Baseline / comparison (this paper)