ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining
This addresses the lack of explainability in GNNs for combinatorial optimization, benefiting researchers and practitioners in graph-based AI, though it is incremental as it builds on existing GNN methods.
The paper tackled the problem of explaining predictions from graph neural networks (GNNs) for combinatorial optimization problems by introducing ARM-Explainer, a post-hoc explainer based on association rule mining, which identified key node features and improved GNN performance on the maximum clique problem, increasing median clique size by 22% on a benchmark dataset.
Numerous graph neural network (GNN)-based algorithms have been proposed to solve graph-based combinatorial optimization problems (COPs), but methods to explain their predictions remain largely undeveloped. We introduce ARM-Explainer, a post-hoc, model-level explainer based on association rule mining, and demonstrate it on the predictions of the hybrid geometric scattering (HGS) GNN for the maximum clique problem (MCP), a canonical NP-hard graph-based COP. The eight most explanatory association rules discovered by ARM-Explainer achieve high median lift and confidence values of 2.42 and 0.49, respectively, on test instances from the TWITTER and BHOSLIB-DIMACS benchmark datasets. ARM-Explainer identifies the most important node features, together with their value ranges, that influence the GNN's predictions on these datasets. Furthermore, augmenting the GNN with informative node features substantially improves its performance on the MCP, increasing the median largest-found clique size by 22% (from 29.5 to 36) on large graphs from the BHOSLIB-DIMACS dataset.