用关联规则挖掘解释图神经网络对最大团问题的预测，并提升性能
ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining
- 基于关联规则挖掘构建后验解释器，识别影响预测的关键节点特征
- 在TWITTER和BHOSLIB-DIMACS数据集上，规则置信度达0.49，提升率22%
- 适合关注GNN可解释性与组合优化性能提升的研究者
众多基于图神经网络（GNN）的算法被用于求解图论组合优化问题（COP），但其预测解释方法仍不成熟。本文提出ARM-Explainer，一种基于关联规则挖掘的后验模型级解释器，应用于混合几何散射（HGS）GNN对最大团问题（MCP）的预测。在TWITTER和BHOSLIB-DIMACS基准数据集的测试实例中，ARM-Explainer发现的8条最具解释性的关联规则，其平均提升值（lift）为2.42，置信度（confidence）为0.49。该方法识别出影响GNN预测的关键节点特征及其取值范围。进一步地，通过引入这些信息丰富的节点特征，显著提升了GNN在MCP上的性能：在BHOSLIB-DIMACS的大规模图上，最大找到团的中位大小从29.5提升至36，增幅达22%。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。