GNNExplainer: Generating Explanations for Graph Neural Networks

• 概
• 符号说明
• 本文方法
• 代码

Ying R., Bourgeois D., You J., Zitnik M. and Leskovec J. GNNExplainer: generating explanations for graph neural networks. In Advances in Neural Information Processing Systems (NIPS), 2019.

概

本文介绍了一种后处理的可解释方案: 即给定一个训练好的 GNN, 对它给予解释.

符号说明

• \(G = (V, E)\), 图;
• \(\mathcal{X} = \{x_1, \ldots, x_n\}, x_i \in \mathbb{R}^d\), \(d\) 维的 node features;
• \(\Phi: G \times \mathcal{X} \rightarrow [C]\), GNN \(\Phi\) 将结点映射为类别 \(c \in \{1, 2, \ldots, C\}\).

本文方法

• 作者希望通过一个结点的 local subgraph 来解释某个结点的预测标签为什么是 \(\hat{y}\). 如上图所示, \(v_i\) 的朋友们都非常享受球类运动, 所以 GNN 预测他可能喜欢篮球.

• 假设完整的图为 \(G_c\), 作者希望为结点 \(v\) 找到一个子图 \(G_S(v) \subset G_c\), 以及部分特征 \(X_S = \{x_j | v_j \in G_S\}\) 来解释 \(v\);

• 首先, 作者希望通过子图 \(G_S, X_S\), 具备足够的预测 \(y(v)\) 的信息, 即:

  \[\tag{2} \max_{G_S} \: MI(Y, (G_S, X_S)) = H(Y) - H(Y|G=G_S, X=X_S), \]

  因为 \(H(Y)\) 是不变的, 所以等价于

  \[-\mathbb{E}_{Y|G_S, X_S} [\log P_{\Phi}(Y|G=G_S, X=X_S)]. \]

  当然了, 如果 \(G_S\) 本身没有限制的话, 它就会倾向于 \(G_c\), 所以我们希望 \(G_S\) 是比较小的:

  \[|G_S| \le K_M. \]

• 但是上述问题其实很难优化, 因为 \(G_S\) 本身是在一个离散的空间上, 很自然地, 作者将邻接矩阵放松到 \(A_S \in [0, 1]^{n \times n}\), 且 \([A_{S}]_{ij} \le [A_c]_{ij}\), 即只有 \(G_c\) 原本存在的边才有可能非零. 我们可以将其理解为边存在的概率, 于是 \(G_S\) 就可以理解为采样得到的一个图, 此时 (2) 需要改写为:

  \[\max_{\mathcal{G}} \: \mathbb{E}_{G_S \sim \mathcal{G}} H(Y|G=G_S, X = X_S), \]

  其中 \(\mathcal{G}\) 是由 \(A_S\) 引出的分布, \(P_{\mathcal{G}}(G_S) = \prod_{(i, j) \in V} [A_{S}]_{ij}\).
  既然信息熵是凹的, 倘若整体关于 \(G_S\) 也是凹的 (虽然实际上不现实, 但是作者的实验证明下面的优化目标用起来还可以), 则:

  \[\max_{\mathcal{G}} \: H(Y|G= \mathbb{E}_{G_S \sim \mathcal{G}} [G_S], X = X_S), \]

• 实际上, 我们可以直接建模 \(\mathbb{E}_{G_S \sim \mathcal{G}} [G_S]\) 为

  \[A_c \odot \sigma(M), \]

  其中 \(M \in \mathbb{R}^{n \times n}\) 为 mask, \(\sigma\) 为 sigmoid 激活函数将其映射到 \([0, 1]\).

• 于是乎, 我们的目标为:

  \[\min_M \: - \log P_{\Phi}(Y=c|G = A_c \odot \sigma(M), X = X_c). \]

  需要注意的是, 为了最后获得稀疏的结果, 需要对 \(M\) 进行截断处理.

• 类似地, 我们可以对特征添加 mask \(F\), 用其为 1 的部分来表示对预测重要的特征部分:

  \[\max_{G_S, F} \: MI(Y, (G_S, X_S)) = H(Y) - H(Y|G=G_S, X=X_S^F := X_S \odot F). \]

  作者说这种建模方式会导致 \(F\) 的值趋向 \(0\) 但是那个特征依旧很重要的情况, 改用如下的建模方式:

  \[X = Z + (X - S) \odot F, \: \sum_{j} F_j \le K_F, \]

  其中 \(Z \in \mathbb{R}^d\) 采样自经验分布.
  注: 这一块不是很理解, 应该是借鉴自图像的可解释 [48].

代码

[official]