Via the top-K approach, it appears like the authors make an implicit assumption about what fraction of edges is important in the graph (a fixed fraction, can't be lower or higher) - in my opinion, this certainly limits the wide applicability of the method. Alternatively, in GNN Explainer [1], they allow up to K edges to explain the label.
The applicability of the method is limited by the graph encoder used (here GNN). 1-WL GNN's are known to be unable to predict links or identify and distinguish certain classes of subgraphs [2][3][4] i.e. GNN's are not well suited for Eq. 5
The work appears to miss relevant baselines like GNN Explainer[1] / CF-GNN Explainer [5]. Moreover the authors ideally should compare with baselines, which enrich GNN's with structural features [6][7][8] (As they are explainable to a certain extent as well). Minor:
The separability of a graph into two subgraphs the causal and non causal might not always be possible? (would this need an encoder which is able to accurately capture the discrete topology over graphs of all orders and sizes - if not I can just make a house into a clique and the label would be incorrectly assigned as 1 because the edges required for the house are present) Please elaborate on this.
The set {s} employed in the test are limited to the ones seen in train.
Moreover, consider a graph with say 20 nodes, and the case where the causal part for instance consists of a house motif and a tree base and the label assigned is 1 or 0 based on the output of House Motif XOR Tree Base - would this be captured by the proposed method (appears like it wont)? References:
1.Ying, Rex, et al. "Gnn explainer: A tool for post-hoc explanation of graph neural networks." arXiv preprint arXiv:1903.03894 (2019).
2.Srinivasan, Balasubramaniam, and Bruno Ribeiro. "On the equivalence between positional node embeddings and structural graph representations." arXiv preprint arXiv:1910.00452 (2019).
3.Dwivedi, Vijay Prakash, et al. "Benchmarking graph neural networks." arXiv preprint arXiv:2003.00982 (2020).
4.Chen, Zhengdao, et al. "Can graph neural networks count substructures?." arXiv preprint arXiv:2002.04025 (2020).
5.Lucic, Ana, et al. "CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks." arXiv preprint arXiv:2102.03322 (2021).
6.Bouritsas, Giorgos, et al. "Improving graph neural network expressivity via subgraph isomorphism counting." arXiv preprint arXiv:2006.09252 (2020).
7.Bodnar, Cristian, et al. "Weisfeiler and lehman go topological: Message passing simplicial networks." arXiv preprint arXiv:2103.03212 (2021).
8.Bodnar, Cristian, et al. "Weisfeiler and lehman go cellular: Cw networks." arXiv preprint arXiv:2106.12575 (2021).
6.Bouritsas, Giorgos, et al. "Improving graph neural network expressivity via subgraph isomorphism counting." arXiv preprint arXiv:2006.09252 (2020).