Exact Subgraph Isomorphism Network for Predictive Graph Mining
This addresses the problem of interpretable graph mining for researchers and practitioners in machine learning, though it is incremental as it builds on existing subgraph and neural network techniques.
The paper tackles the challenge of achieving high discriminative ability and interpretability in graph-level prediction by proposing the Exact subgraph Isomorphism Network (EIN), which combines exact subgraph enumeration, neural networks, and sparse regularization, resulting in sufficiently high prediction performance compared to standard graph neural network models.
In the graph-level prediction task (predict a label for a given graph), the information contained in subgraphs of the input graph plays a key role. In this paper, we propose Exact subgraph Isomorphism Network (EIN), which combines the exact subgraph enumeration, neural network, and a sparse regularization. In general, building a graph-level prediction model achieving high discriminative ability along with interpretability is still a challenging problem. Our combination of the subgraph enumeration and neural network contributes to high discriminative ability about the subgraph structure of the input graph. Further, the sparse regularization in EIN enables us 1) to derive an effective pruning strategy that mitigates computational difficulty of the enumeration while maintaining the prediction performance, and 2) to identify important subgraphs that contributes to high interpretability. We empirically show that EIN has sufficiently high prediction performance compared with standard graph neural network models, and also, we show examples of post-hoc analysis based on the selected subgraphs.