ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Neural NetworkSimilar Papers 제목 키워드 기반
Parameterized Explainer for Graph Neural Network
Despite recent progress in Graph Neural Networks (GNNs), explaining predictions made by GNNs remains a challenging open problem. The leading method independently addresses the local explanations (i.e., important subgraph…
Graph ClassificationGraph Neural NetworkExplainability in subgraphs-enhanced Graph Neural Networks
Recently, subgraphs-enhanced Graph Neural Networks (SGNNs) have been introduced to enhance the expressive power of Graph Neural Networks (GNNs), which was proved to be not higher than the 1-dimensional Weisfeiler-Leman i…
Graph ClassificationExplaining Knowledge Graph Embedding via Latent Rule Learning
Knowledge Graph Embeddings (KGEs) embed entities and relations into continuous vector space following certain assumption, and are a powerful tools for representation learning of knowledge graphs. However, following vecto…
Graph EmbeddingKnowledge DistillationKnowledge Graph EmbeddingKnowledge Graph Embeddings+4PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks
In Graph Neural Networks (GNNs), the graph structure is incorporated into the learning of node representations. This complex structure makes explaining GNNs' predictions become much more challenging. In this paper, we pr…
PredictionGNNExplainer: Generating Explanations for Graph Neural Networks
Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs.GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. Howeve…
BIG-bench Machine LearningExplainable artificial intelligenceGraph ClassificationGraph Neural Network+1