Explaining GNN-based Recommendations in Logic

Download PDF

Abstract

This paper proposes Makex (MAKE senSE), a logic approach to ex-This paper proposes Makex (MAKE senSE), a logic approach to explaining why a GNN-based model M( 𝐿,𝑀 ) recommends item 𝑀 to user 𝐿 . It proposes a class of Rules for ExPlanations, denoted as REPs and de!ned with a graph pattern Q and dependency 𝑁 →M( 𝐿,𝑀 ) , where 𝑁 is a collection of predicates, and the model M( 𝐿,𝑀 ) is treated as the consequence of the rule. Intuitively, given M( 𝐿,𝑀 ) , we discover pattern Q to identify relevant topology, and precon-we discover pattern Q to identify relevant topology, and precondition 𝑁 to disclose correlations, interactions and dependencies of vertex features; together they provide rationals behind prediction M( 𝐿,𝑀 ) , identifying what features are decisive for M to make pre-M( 𝐿,𝑀 ) , identifying what features are decisive for M to make predictions and under what conditions the decision can be made. We (a) de!ne REPs with 1-WL test, on which most GNN models for recommendation are based; (b) develop an algorithm for discov-recommendation are based; (b) develop an algorithm for discovering REPs for M as global explanations, and (c) provide a top- 𝑂 algorithm to compute top-ranked local explanations. Using real-life graphs, we empirically verify that Makex outperforms previous explanation methods in terms of fidelity, sparsity and effciency.