Explaining Graph Neural Networks via Structure-aware Interaction Index

Overview

• The Shapley value is a popular tool for interpreting black-box machine learning models, but it has limitations when dealing with structured inputs like graph neural networks.
• This paper introduces the Myerson-Taylor interaction index, which incorporates the graph structure into the attribution of node values and node interactions.
• The authors prove that the Myerson-Taylor index is the unique index that satisfies a set of five natural axioms accounting for graph structure and high-order interactions.
• The paper proposes Myerson-Taylor Structure-Aware Graph Explainer (MAGE), which uses the second-order Myerson-Taylor index to identify the most important motifs influencing the model prediction.
• Experiments show that MAGE provides superior subgraph explanations compared to state-of-the-art methods.

Plain English Explanation

Machine learning models are often treated as "black boxes," meaning it can be difficult to understand how they make their predictions. The Shapley value is a popular tool for interpreting these black-box models, but it has limitations when dealing with complex, structured data like graph neural networks.

This paper introduces a new approach called the Myerson-Taylor interaction index, which is designed to better account for the graph structure of the input data. Unlike the Shapley value, the Myerson-Taylor index decomposes the input into components that satisfy a specific connectivity criterion, allowing it to capture the importance of different subgraphs or "motifs" within the larger graph.

The authors prove that the Myerson-Taylor index is the unique index that satisfies a set of five natural axioms, which ensure that it properly accounts for the graph structure and high-order interactions between nodes. This strong theoretical foundation is what makes the Myerson-Taylor index a promising tool for interpreting graph-based machine learning models.

Building on this, the researchers propose a novel explainer called MAGE (Myerson-Taylor Structure-Aware Graph Explainer), which uses the second-order Myerson-Taylor index to identify the most important motifs that are influencing the model's predictions, both positively and negatively. Through extensive experiments, they show that MAGE consistently provides better explanations than other state-of-the-art methods, especially for graph-based models.

Technical Explanation

The key innovation in this paper is the introduction of the Myerson-Taylor interaction index, which addresses limitations of the Shapley value when applied to graph-structured data.

Unlike the Shapley value, which either focuses solely on node-wise importance or neglects the graph structure when perturbing the input, the Myerson-Taylor index internalizes the graph structure into the attribution of node values and interaction values. Specifically, it decomposes coalitions (sets of nodes) into components that satisfy a pre-chosen connectivity criterion, rather than treating each node independently.

The authors prove that the Myerson-Taylor index is the unique index that satisfies a system of five natural axioms accounting for graph structure and high-order interaction among nodes. These axioms ensure properties like linearity, efficiency, and the ability to capture both node importance and higher-order interactions.

Leveraging these desirable properties, the researchers propose MAGE, a novel explainer that uses the second-order Myerson-Taylor index to identify the most important motifs (subgraphs) influencing the model's predictions. MAGE outperforms state-of-the-art methods like KernelSHAP-IQ and Error Analysis on various graph datasets and models, providing superior subgraph explanations.

Critical Analysis

The Myerson-Taylor interaction index and the MAGE explainer presented in this paper offer a promising approach to interpreting graph-based machine learning models. The strong theoretical foundation, with the index satisfying a set of natural axioms, is a compelling aspect of this work.

However, the paper does not extensively discuss the limitations or potential downsides of the Myerson-Taylor index. For example, the computational complexity of computing the index is not explored, which could be a practical concern for large-scale graphs. Additionally, the paper does not delve into the robustness of the index to noise or perturbations in the input graph, which would be an important consideration for real-world applications.

Furthermore, while the experiments demonstrate the superiority of MAGE over other state-of-the-art methods, the paper does not provide a deep analysis of the specific cases where MAGE excels or where it may fall short. A more nuanced discussion of the strengths and weaknesses of the proposed approach would help readers better assess its overall merits and limitations.

Conclusion

This paper introduces the Myerson-Taylor interaction index, a novel tool for interpreting graph-based machine learning models. By incorporating the graph structure into the attribution of node values and interactions, the Myerson-Taylor index addresses key limitations of the Shapley value and other existing explainability approaches.

The authors prove that the Myerson-Taylor index is the unique index satisfying a set of natural axioms, ensuring its strong theoretical grounding. Building on this, they propose the MAGE explainer, which leverages the second-order Myerson-Taylor index to identify the most influential subgraph motifs for a model's predictions.

Empirical results demonstrate that MAGE consistently outperforms state-of-the-art explainability methods, highlighting the potential of the Myerson-Taylor index to advance the interpretability of graph neural networks and other graph-based models. As the use of such models continues to grow, tools like MAGE could play a crucial role in enhancing the transparency and trustworthiness of these powerful machine learning techniques.