Existing explanation methods for GNN typically apply the following approach

$$G^* = \argmin_{G'} I(G, G') - \alpha I(Y, G'),$$

where $G'$ is a candidate explanatory subgraph, $Y$ is the label, and $\alpha$ is a balance parameter. However, $G'$ often deviates from the distribution of original graphs.

To mitigate the OOD issue, this paper introduces the concept of proxy graphs. They reformulate the estimation of $P(Y|G')$ as follows:

$$P(Y|G') = \mathbb{E}_{\tilde{G} \sim P_{\mathcal{G}}}[P(Y|\tilde{G}) \cdot P(\tilde{G}|G')]$$

where $P_{\mathcal{G}}$ denotes the distribution of $\tilde{G}$.

The main idea of ProxyGraph is to generate an in-distribution proxy graph,$\tilde{G}$, using the explanatory subgraph, $G'$, ensuring that the label information preserved in $\tilde{G}$ closely resembles that in $G'$.

I also found that they consider only the edges in the graph when generating explanations. To overcome the out-of-distribution problem, they enforce $p(\hat{G})$ to be close to $p(G)$. To achieve this, they propose the following objective:

$$ KL(p(\hat{G})|p(G)) $$

However, since this objective is intractable, they propose a tractable loss function, defined as follows:

$$ \text{Cross-Entropy}(A_{\hat{G}}, A_{G}) = \frac{\beta}{|\mathcal{E}|} \sum_{(u, v) \in \mathcal{E}} \log \left(\tilde{p}_{u v}\right)+\frac{1}{|\overline{\mathcal{E}}|} \sum_{(u, v) \in \overline{\mathcal{E}}} \log \left(1-\tilde{p}_{u v}\right). $$

where $\mathcal{E}$ is the set of node pairs that are connected in $G$, $\mathcal{\overline{E}}$ is the set of node pairs that are unconnected in $G$, and $p_{uv}$ is the probability that an edge exists between node $u$ and $v$ in $\hat{G}$. In other words, they use the absence or existence of an edge in the graph to describe the distribution of the graph. $A_G$ is the adjacency matrix of the original graph, and $A_{\hat{G}}$ represents the adjacency matrix of the explantory subgraph.

References

Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks ICML 2024