EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time

[OpenReivew] [arXiv]

Run Our Code:

$ python main.py --dataset ba_2motifs --gnn gin --sparsity 0.7 --do_plot 0 --linear_search 1

• Graph classificiation dataset options: ba_2motifs, Mutagenicity, MUTAG, NCI1

• Node classificiation dataset options: ba_shape, ba_communicity, trid_grid

• GNN varients: gin, gcn, sage

• Sparsity range: 0.0~1.0 (For graph classificiation)

• Topk values： even integers (For node classificiation) E.g., If you want to select top 6 undirected edges, enter 12. It means equivalently top 12 directed edges.

• do_plot: 1 if want to visualize, else 0

• linear_search: 1 if turn on the linear-complexity search module, else 0

Environment:

CUDA 11.3
python 3.9.18
pytorch 1.11.0
pytorch-cluster 1.6.0
pytorch-cuda 11.8
pytorch-memlab 0.3.0
pytorch-mutex 1.0
pytorch-scatter 2.0.9
pytorch-sparse 0.6.15
pyg 2.1.0
numpy 1.26.3
ninja 1.10.2
networkx 3.2.1

Cite our paper:

@inproceedings{
lu2024eig,
title={{EiG-Search}: Generating Edge-Induced Subgraphs for {GNN} Explanation in Linear Time},
author={Shengyao Lu and Bang Liu and Keith G Mills and Jiao He and Di Niu},
booktitle={Forty-first International Conference on Machine Learning},
year={2024},
}