GnnExplainer loss function and node/edge feature mask learning

[ashkspark]

My understanding is that in GNNExplainer method we are trying to find an edge as well as a feature mask to minimize the following loss function.

where \alpha and \beta are constants. My question is about learning binary feature selector ‘F’. In the paper, they mention that the binary mask that they introduced ignores features that are important for prediction but take values close to zero. They further said one can use marginalization over all feature subset and employ a Monter Carlo estimate. See this part from the paper:

They further mentioned that they use a reparameterization technique in the back propagation process.

Questions:

i) Are these two properties, i.e., M.C. estimate and reparameterization techniques implemented in GNNExplainer’s implementation in PyG?

ii) Are there any examples of using binary feature mask to generate an explanation or feature importance for traditional supervised models? Because it seems to me this way of generating feature importance fails to consider feature interaction to find the corresponding feature attribution when compared to other methods like Shapley? Why is it ok to learn such a mask for graphs but not generally ok for traditional ML models?

[rusty1s]

1. Hey @ashkspark, sorry for my super late reply. This is currently no implemented in our GNNExplainer implementation, and I am even unable to find it in the official implementation. I am sure @RexYing can help out here :)

2. Can you clarify what you mean by feature interaction? You are right that the current attributions cannot explain phenomenons such as "these features generally need to appear together".

[RexYing]

1. @ashkspark For reparameterization, only datasets with node features (where there is also a need to extract important feature dimensions) are needed and would not be applicable to general graph datasets and didn't fit the api as well.

But the implementation is simple: we sample Z according to the feature distribution of the training set for every feature dimension (I only experimented on categorical features, in which case we just sample by class probability of the categorical feature); and then apply the mask F using that formula. So for each feature dimension, when F=0, you get the randomly sampled Z according to the marginal, which means the feature is not important. When F=1, you recover X which means the feature dimension is important. And then we can threshold out the unimportant dimensions just as how we threshold out unimportant edges.

2. So subgraphX (also implemented in pyg) considers shapley value for the subset of important edges. Similar approach can be considered for node feature as well. It should be possible to integrate SHAP / LIME with edge-mask-based explainability methods.
   Since the objective is to find the concise subset of nodes that maximally approximate the model prediction / ground truths, it's not really feature importance in the sense of shapley values (aggregated over multiple possible combinations of feature subset). It's rather the set of edges that best explain the model prediction (and exclude redundant feature / edges for the prediction). So it's like a max rather than a weighted sum, if that makes sense to you. In that sense it's also considering interactions among features / edges (unlike occlusion), but not over all possible combinations. I think it's possible to do this for traditional models, if by traditional you consider those that are also done by backprop. It won't be applicable for those that do not do sgd-like optimizations.

[ashkspark]

Thank you both. @rusty1s, @RexYing