Determining graphlet explanations for machine learning on graphs

What is it about?

This article looks at the graph/network domain for explaining graph machine learning models. Explanations are identified as subgraphs and as the motif that constitutes the explanatory subgraph. Such explanations highlight the part in the input-level graph that are the most relevant for a certain prediction, through measuring prediction degradation when the explanatory subgraph is removed and when the graph is reduced to the explanatory subgraph. The large space of possible explanatory subgraphs is explored with a genetic algorithm using multiple objectives which facilitate desirable properties of explanations (fidelity-minimum prediction degradation, and sparsity-explanation size).

Featured Image

Why is it important?

It is more and more realized that many real world data is the best represented by connected or disconnected components. Simple case are graphs or networks where pairwise connections are part of the data representation. Subgraphs represent combination of these pairwise connections, and are often used to explain some property of the entire graph. Motifs show reoccurring subgraph patterns, therefore are relevant for concise and human-intelligible representation of subgraphs. Machine learning is ubiquitous nowadays, and explainability is increasingly relevant for machine learning as models get more complex and less interpretable. Similarly, machine learning models that operate on graph-structured data are getting more complex. Knowing why a machine learning model makes certain decisions can aid knowledge discovery and is critical in high-stakes applications. The method provides input-level explanations and is model model agnostic, meaning it can be used with any machine learning model operating on graph-structured data.