Explaining Graph Neural Networks

Fabrizio Silvestri

​

Artificial Intelligence for Biomedical Applications - AI4BA 2024

26 Giugno 2024

Introduction to eXplainable AI (XAI)

Where we begin our journey on XAI…

AI4BA 2024 - June 26, 2024

Complexity vs. Explainability

AI4BA 2024 - June 26, 2024

Simple models are less expressive but explainable

• e.g., linear/logistic regression coefficients are easily interpretable

Simple Decision Boundary Surface

Complexity vs. Explainability

AI4BA 2024 - June 26, 2024

Complex models are more effective but opaque

• e.g., million/billion-parameter NN

Convoluted Decision Boundary Surface

The Need for XAI

• AI/ML systems are widely deployed to support decision-making processes in several application contexts
• In many critical domains, highly accurate predictions are not enough!
• Healthcare: A physician must be able to tell their patient the rationale behind an AI/ML-based diagnosis
• Finance: A banker must be able to tell their customer why they won’t grant them a loan
• …

AI4BA 2024 - June 26, 2024

The Need for XAI

• Several attempts have been made to promote XAI as part of broader data privacy regulation initiatives
• EU GDPR (General Data Protection Regulation)
• HIPAA (Health Insurance Portability and Accountability Act) Privacy Rule
• CCPA (California Consumer Privacy Act)
• PCI DSS (Payment Card Industry Data Security Standard)
• NIST AI Risk Management Framework
• …

AI4BA 2024 - June 26, 2024

What Does Explainable Mean?

• In the pre-deep-learning era, some models are inherently explainable
• Explanations are part of the model

AI4BA 2024 - June 26, 2024

Decision Trees

Linear Regression

What Does Explainable Mean?

• Black-box models may explain their predictions via heatmap visualization

AI4BA 2024 - June 26, 2024

Natural Language Processing

Computer Vision

What Does Explainable Mean?

• Black-box models may explain their predictions via prototypical examples or natural language sentences

AI4BA 2024 - June 26, 2024

Properties of Explanations

• Faithfulness → How to provide explanations that accurately represent the true reasoning behind the model’s final decision
• Plausibility → Is the explanation correct or something we can believe is true, given our current knowledge of the problem?
• Understandable → Can I put it in terms that end user without in-depth knowledge of the system can understand?
• Stability → Does similar instances have similar interpretations?

AI4BA 2024 - June 26, 2024

Properties of Explanations

• Faithfulness → How to provide explanations that accurately represent the true reasoning behind the model’s final decision
• Plausibility → Is the explanation correct or something we can believe is true, given our current knowledge of the problem?
• Understandable → Can I put it in terms that end user without in-depth knowledge of the system can understand?
• Stability → Does similar instances have similar interpretations?

AI4BA 2024 - June 26, 2024

Properties of Explanations

• Faithfulness → How to provide explanations that accurately represent the true reasoning behind the model’s final decision
• Plausibility → Is the explanation correct or something we can believe is true, given our current knowledge of the problem?
• Understandable → Can I put it in terms that end user without in-depth knowledge of the system can understand?
• Stability → Does similar instances have similar interpretations?

AI4BA 2024 - June 26, 2024

Properties of Explanations

• Faithfulness → How to provide explanations that accurately represent the true reasoning behind the model’s final decision
• Plausibility → Is the explanation correct or something we can believe is true, given our current knowledge of the problem?
• Understandable → Can I put it in terms that end user without in-depth knowledge of the system can understand?
• Stability → Does similar instances have similar interpretations?

AI4BA 2024 - June 26, 2024

Evaluating Explanations

• Application level evaluation → Put the model in practice and have the end users interact with explanations to see if they are useful
• Human evaluation → Set up a Mechanical Turk task and ask non-experts to judge the explanations
• Functional evaluation → Design metrics that directly test properties of your explanation

AI4BA 2024 - June 26, 2024

Evaluating Explanations

• Application level evaluation → Put the model in practice and have the end users interact with explanations to see if they are useful
• Human evaluation → Set up a Mechanical Turk task and ask non-experts to judge the explanations
• Functional evaluation → Design metrics that directly test properties of your explanation

AI4BA 2024 - June 26, 2024

Evaluating Explanations

• Application level evaluation → Put the model in practice and have the end users interact with explanations to see if they are useful
• Human evaluation → Set up a Mechanical Turk task and ask non-experts to judge the explanations
• Functional evaluation → Design metrics that directly test properties of your explanation

AI4BA 2024 - June 26, 2024

Local vs. Global Explanations

AI4BA 2024 - June 26, 2024

Do we explain individual predictions?

Examples:

Heatmaps, Rationales

Do we explain the entire model?

Examples:

Linear Regression, Decision Trees, Prototypes

Local Explanations

Global Explanations

Ante vs. Post Hoc Explanations

AI4BA 2024 - June 26, 2024

Is the model inherently explainable?

Examples:

Rationales, Linear Regression, Decision Trees

Do we need an external method to explain the black-box model?

Examples:

Heatmaps (some), Counterfactuals

Ante-Hoc

Post-Hoc

Model-Based vs Model-Agnostic Explanations

AI4BA 2024 - June 26, 2024

Can it explain only one model?

Examples:

Rationales, Linear Regression, Decision Trees, Attention, Gradients (differentiable), GNNs

Can it explain any model?

Examples:

LIME (Locally Interpretable Model-Agnostic Explanations), SHAP (Shapley Values), ReLAX

Model-Based

Model-Agnostic

Two (famous) Examples

Where we continue our journey with two examples on data different than graphs …

​

Slides courtesy of Prof. Gabriele Tolomei.

AI4BA 2024 - June 26, 2024

Explainable AI: Taxonomy

Source: https://www.researchgate.net/figure/Taxonomy-of-explainable-artificial-intelligence_fig2_349914003

Explainable AI: Taxonomy

LIME �(Locally Interpretable Model-Agnostic Explanations)

black box

(e.g., deep NN)

LIME �(Locally Interpretable Model-Agnostic Explanations)

black box

(e.g., deep NN)

LIME �(Locally Interpretable Model-Agnostic Explanations)

black box

(e.g., deep NN)

LIME �(Locally Interpretable Model-Agnostic Explanations)

black box

(e.g., deep NN)

(linear model)

LIME �(Locally Interpretable Model-Agnostic Explanations)

black box

(e.g., deep NN)

(linear model)

LIME �(Locally Interpretable Model-Agnostic Explanations)

black box

(e.g., deep NN)

(linear model)

As close as possible

LIME: Intuition

LIME: Example (Image Classification)

A data point (image)

LIME: Example (Image Classification)

A data point (image)

black box

LIME: Example (Image Classification)

A data point (image)

black box

"frog"

Its predicted class

LIME: Example (Image Classification)

A data point (image)

black box

"frog"

Its predicted class

Why Does the Model Output "frog"?

LIME: Example (Image Classification)

Represent each image as a set of superpixels (segments)

LIME: Example (Image Classification)

Represent each image as a set of superpixels (segments)

Randomly delete some segments to generate samples in the neighborhood of the data point to explain

LIME: Example (Image Classification)

Input these samples to the black-box model and compute P("frog" | )…

black box

black box

black box

LIME: Example (Image Classification)

Use predictions from the black-box as labels to train a linear model

0.85

0.52

0.01

M = #segments

black-box labels

LIME: Example (Image Classification)

Interpret the model just learned

LIME: Example (Image Classification)

Interpret the model just learned

For each segment i, look at the corresponding weight

LIME: Example (Image Classification)

Interpret the model just learned

For each segment i, look at the corresponding weight

Segment i is not related to "frog"

LIME: Example (Image Classification)

Interpret the model just learned

For each segment i, look at the corresponding weight

Segment i is not related to "frog"

Segment i indicates the image is "frog"

LIME: Example (Image Classification)

Interpret the model just learned

For each segment i, look at the corresponding weight

Segment i is not related to "frog"

Segment i indicates the image is "frog"

Segment i indicates the image is not "frog"

LIME: Pseudocode

Explainable AI: Taxonomy

SHAP: Feature Attribution

• Based on Shapley Values, an old idea from game theory (1953)

​

SHAP: Feature Attribution

• Based on Shapley Values, an old idea from game theory (1953)
• Analogy: A cooperative game (ML/AI model) with a set of players (features) trying to achieve a goal (a correct prediction)

SHAP: Feature Attribution

• Based on Shapley Values, an old idea from game theory (1953)
• Analogy: A cooperative game (ML/AI model) with a set of players (features) trying to achieve a goal (a correct prediction)
• Different from simple "feature importance" plots we are used to!

​

SHAP: Feature Attribution

• Consistency → If we add more features to the model, we expect the importance of previous features not to decrease

SHAP: Feature Attribution

• Consistency → If we add more features to the model, we expect the importance of previous features not to decrease
• Accuracy → If we have chosen a metric to measure the importance of a model, then the attribution of each feature should add up to that metric

SHAP: Feature Attribution

• Consistency → If we add more features to the model, we expect the importance of previous features not to decrease
• Accuracy → If we have chosen a metric to measure the importance of a model, then the attribution of each feature should add up to that metric
• Insightfulness → We must realize if a feature contributes to lower or increase model outputs (feature ranking is not enough!)

SHAP: Shapley Values

• Intuition: In a multi-player cooperative game, sometimes a player value in a team could be greater than their value as an individual

SHAP: Shapley Values

• Intuition: In a multi-player cooperative game, sometimes a player value in a team could be greater than their value as an individual
• In an ML/AI setting, a Shapley Value is the contribution of a feature value to the difference between the actual and the mean prediction

SHAP: Shapley Values

• Intuition: In a multi-player cooperative game, sometimes a player value in a team could be greater than their value as an individual
• In an ML/AI setting, a Shapley Value is the contribution of a feature value to the difference between the actual and the mean prediction
• Analogous to answering the following question: Since with no features we would just predict the average outcome, how much the prediction changes if we bring in the first feature?

SHAP: Shapley Values

SHAP: Shapley Values

Weighted average across

SHAP: Shapley Values

Weighted average across

Contribution from adding player

SHAP: Shapley Values

Given an ordering, each player contributes when added to the preceding ones:

SV is the average contribution across all orderings

Intuitive meaning in terms of player orderings

SHAP: Application to ML/AI

• Consider features as players

SHAP: Application to ML/AI

• Consider features as players
• Consider model behavior as profit
• e.g., the prediction, the loss, etc.

SHAP: Application to ML/AI

• Consider features as players
• Consider model behavior as profit
• e.g., the prediction, the loss, etc.
• Then, use Shapley Values to quantify each feature’s impact

SHAP: Application to ML/AI

• Consider features as players
• Consider model behavior as profit
• e.g., the prediction, the loss, etc.
• Then, use Shapley Values to quantify each feature’s impact
• SHAP uses Shapley Values to explain individual predictions (local)

Feature Importance vs. SHAP Importance

Wine Dataset

Feature Importance vs. SHAP Importance

Wine Dataset

Training XGBoost for binary classification

Feature Importance vs. SHAP Importance

Wine Dataset

Training XGBoost for binary classification

Feature Importance

Feature Importance vs. SHAP Importance

Wine Dataset

Training XGBoost for binary classification

Feature Importance

`Total Sulfur Dioxide` is the most important feature according to the model, but we cannot tell whether it triggers 0 or 1 prediction

Feature Importance vs. SHAP Importance

SHAP Importance

Feature Importance vs. SHAP Importance

SHAP Importance

SHAP importance averages feature contribution for each row in the dataset

Feature Importance vs. SHAP Importance

SHAP importance averages feature contribution for each row in the dataset

SHAP Importance

They are totally different from XGBoost feature importance!

Feature Importance vs. SHAP Importance

SHAP Importance

They are totally different from XGBoost feature importance!

Tree attribution methods give more value to features far away from the root

Counterintuitive

SHAP importance averages feature contribution for each row in the dataset

Feature Importance vs. SHAP Importance

SHAP can be used to extract local explanations via Force plots

Feature Importance vs. SHAP Importance

SHAP can be used to extract local explanations via Force plots

They tell us how much feature contributed to make the prediction diverge from a base value (average prediction with no features)

Feature Importance vs. SHAP Importance

SHAP can be used to extract local explanations via Force plots

They tell us how much feature contributed to make the prediction diverge from a base value (average prediction with no features)

Low values of `Total Sulfur Dioxide` (mean=30) push the output towards a positive prediction, while `Sulphates` does the opposite

SHAP: Many Visualization Tools

• Beeswarm plots

SHAP: Many Visualization Tools

• Beeswarm plots
• Bar plots

SHAP: Many Visualization Tools

• Beeswarm plots
• Bar plots
• Waterfall plots

SHAP: Many Visualization Tools

• Beeswarm plots
• Bar plots
• Waterfall plots
• Dependence plots
• …

GNN-Explainer

Where we show the first example of an XAI method for GNNs …

​

Some slides are courtesy of Prof. Simone Scardapane.

AI4BA 2024 - June 26, 2024

AI4BA 2024 - June 26, 2024

GNNs are Powerful but …

• Lack transparency
• they do not easily allow for a human-intelligible explanation of their predictions
• The ability to understand GNN’s predictions is important and useful:
• it can increase trust in the GNN model
• it improves model’s transparency in a growing number of decision-critical applications pertaining to fairness, privacy and other safety challenges
• it allows practitioners to get an understanding of the network characteristics, identify and correct systematic patterns of mistakes made by models before deploying them in the real world.

AI4BA 2024 - June 26, 2024

GNNExplainer in a Nutshell

• GNNExplainer takes a trained GNN and its prediction(s), and it returns an explanation in the form of a small subgraph of the input graph together with a small subset of node features that are most influential for the prediction(s)

AI4BA 2024 - June 26, 2024

GNNExplainer Characteristics

• GNN-Model Agnostic
• It works on any graph and on any task
• Single and Multi-instance Explanations
• In the case of single-instance explanations, GNNExplainer explains a GNN’s prediction for one particular instance (i.e., a node label, a new link, a graph-level label).
• In the case of multi-instance explanations, GNNExplainer provides an explanation that consistently explains a set of instances (e.g., nodes of a given class)
• GNNExplainer specifies an explanation as a rich subgraph of the entire graph the GNN was trained on, such that the subgraph maximizes the mutual information with GNN’s prediction(s)

AI4BA 2024 - June 26, 2024

GNNExplainer Characteristics

• For graphs, it is fundamental that the resulting subgraph is small, since visualizing and interpreting it is complex.
• For this reason, tailored methods have been proposed to force sparsity as the main concern.
• GNNExplainer works by optimizing the masks using the following criteria:
• Keeping the original prediction consistent;
• Having small masks (l1 regularization);

AI4BA 2024 - June 26, 2024

GNNExplainer: Problem Formulation

• The computation graph of node v, which is defined by the GNN’s neighborhood-based aggregation fully determines all the information the GNN uses to generate prediction ŷ at node v. In particular, v’s computation graph tells the GNN how to generate v’s embedding z.

AI4BA 2024 - June 26, 2024

GNNExplainer: Problem Formulation

• G_c(v) is the computation graph
• A_c(v) ∈ {0,1}^nxn is the adjacency matrix
• The GNN model Φ learns P_Φ(Y|G_c,X_c), where Y is r.v. representing labels {1, …, C}
• ŷ = Φ(G_c(v),X_c(v)) ⇒ We only need graph structure G_c(v) and node features X_c(v) to explain ŷ

AI4BA 2024 - June 26, 2024

GNNExplainer: Problem Formulation

• GNNExplainer generates explanation for prediction ŷ as (G_S,X^F_S)
• G_S is a small subgraph of the computation graph
• X_S is the associated feature of G_S
• X^F_S is a small subset of node features
• masked out by the mask F, i.e., X^F_S = { x_j^F |v_j ∈ G_S} that are most important for explaining ŷ

AI4BA 2024 - June 26, 2024

GNNExplainer: Single-Instance Explanations

• Given a node v, our goal is to identify a subgraph G_S ⊆ G_c and the associated features X_S = { x_j | v_j ∈ G_S} that are important for the GNN’s prediction ŷ.
• We formalize the notion of importance using mutual information MI���
• For node v, MI quantifies the change in the probability of prediction ŷ = Φ(G_c,X_c) when v’s computation graph is limited to explanation subgraph G_S and its node features are limited to X_S.

AI4BA 2024 - June 26, 2024

GNNExplainer: Single-Instance Explanations

• H(Y) is constant ⇒ we just need to minimize the conditional entropy which can be expressed as follows:��
• To obtain a compact explanation, we impose an additional constraint on G_S’s size as: |G_S|≤ K_M, so that G_S has at most K_M nodes.

AI4BA 2024 - June 26, 2024

Optimization Framework

AI4BA 2024 - June 26, 2024

Prediction should stay consistent

The mask should be sparse

Weights should be as close as possible to 0 or 1

Experiments: Datasets

AI4BA 2024 - June 26, 2024

• MUTAG is a dataset of 4,337 molecule graphs labeled according to their mutagenic effect on the Gram-negative bacterium S. typhimurium
• Reddit-Binary is a dataset of 2,000 graphs, each representing an online discussion thread on Reddit.
• Nodes are users participating in a thread
• Edges indicate that one user replied to another user’s comment
• Graphs are labeled according to the type of user interactions in the thread:
• r/IAmA and r/AskReddit contain Question-Answer interactions
• r/TrollXChromosomes and r/atheism contain Online-Discussion interactions

Experiments: Qualitative Results

AI4BA 2024 - June 26, 2024

Experiments: Qualitative Results

AI4BA 2024 - June 26, 2024

Experiments: Qualitative Results

AI4BA 2024 - June 26, 2024

Experiments: Qualitative Results

AI4BA 2024 - June 26, 2024

PGExplainer

Where we show a more advanced example of an XAI method for GNNs …

​

Some slides are courtesy of Prof. Simone Scardapane.

AI4BA 2024 - June 26, 2024

AI4BA 2024 - June 26, 2024

PGExplainer in a Nutshell

AI4BA 2024 - June 26, 2024

PGExplainer Characteristics

• GNN-Model Agnostic
• It works on any graph and on any task
• PGExplainer specifies an explanation as a subgraph of the entire graph the GNN was trained on
• Also in this case we pick the subgraph maximizes the mutual information with GNN’s prediction(s)

AI4BA 2024 - June 26, 2024

PGExplainer Learning Objectives

• The original input graph G_o is divided into 2 subgraphs:�G_o = G_s + ∆G
• G_s is the expected explanatory subgraph
• ∆G task-irrelevant edges
• Y_o is the GNN’s output.
• PGExplainer finds G_s by maximizing the mutual information between the GNN’s predictions and the underlying structure G_s

AI4BA 2024 - June 26, 2024

PGExplainer: Selecting G_s is intractable …

• Assume G_s is a Gilbert Random Graph
• Each edge in G_s is selected from G_o u.a.r and independently with prob. P(e_ij) ~ Bern(θ_ij), i.e., P(e_ij = 1) = θ_ij�
• Thus P(G_s) = Π_{(i,j)∈Edges} θ_ij�
• The objective can be then rewritten as���where q(Θ) is the distribution of the explanatory graph parameterized by θ’s

AI4BA 2024 - June 26, 2024

PGExplainer: Reparametrization Trick

• Sampling G_s ~ q(Θ) is non-differentiable, so…
• We approximate the sampling process G_s ∼ q(Θ) with G_s ≈ Ĝ_s = f_Ω(G_o, τ, ε) with parameters Ω, where�
• the temperature τ to control the approximation
• an independent random variable ε to control the sampling�
• The edge weight ê_ij is calculated by���σ is the sigmoid function, and ω_ij ∈ ℝ is the parameter

AI4BA 2024 - June 26, 2024

PGExplainer: Reparametrization Trick

• After the reparametrization the optimization becomes:�
• And we modify the conditional entropy with H(Yo, Ŷ_s), where Ŷ_s is the prediction of the GNN model with Ĝ_s as the input.
• With the above relaxations, we adopt Monte Carlo (K times) to approximately optimize the objective function:

AI4BA 2024 - June 26, 2024

PGExplainer: Reparametrization Trick

• Sampling G_s ~ q(Θ) is non-differentiable, so…

AI4BA 2024 - June 26, 2024

PGExplainer: Experiments

AI4BA 2024 - June 26, 2024

PGExplainer: Experiments

AI4BA 2024 - June 26, 2024

ProtGNN

Where we show a self-explainable method for GNNs …

AI4BA 2024 - June 26, 2024

AI4BA 2024 - June 26, 2024

ProtGNN: Characteristics

• Subgraph-based
• It extracts a Prototype Graph Neural Network
• Which uses a GNN as an encoder and adds a decoder

AI4BA 2024 - June 26, 2024

ProtGNN: Characteristics

AI4BA 2024 - June 26, 2024

ProtGNN: GNN Encoder

AI4BA 2024 - June 26, 2024

• For a given input graph x_i, the graph encoder f maps the whole graph into a single graph embedding h with a fixed length
• The encoder could be any backbone GNN e.g., GCN, GAT or GIN
• The graph embedding h could be obtained by taking a sum or max pooling of the last GNN layer

ProtGNN: Prototypes

AI4BA 2024 - June 26, 2024

• First we allocate a pre-determined number of prototypes m for each class
• A prototype is a data value that reflects other values in its class, e.g., a vector
• In the final trained ProtGNN, each class can be represented by a set of learned prototypes
• The prototypes should capture the most relevant graph patterns for�identifying graphs of each class

ProtGNN: Prototype Layer g_P

AI4BA 2024 - June 26, 2024

• For each input graph x_i and its embedding h, the prototype layer computes the similarity scores:���where p_k is the k-th prototype with the same dimension as the graph embedding h
• sim is monotonically decreasing to ‖p_k − h‖₂ and�always greater than zero
• In experiments, is set to a small value e.g., 10^-4

ProtGNN: Fully Connected Layer c

AI4BA 2024 - June 26, 2024

• The similarity scores, the fully connected layer with softmax computes the output probabilities for each class

ProtGNN: Learning Objective

AI4BA 2024 - June 26, 2024

• The goal is to learn a ProtGNN with both accuracy and inherent interpretability.
• For accuracy, we minimize the cross-entropy loss on the training dataset: 1/n ∑CrsEnt(c◦g_p◦f(x_i), y_i)
• For better interpretability, we consider several constraints in constructing prototypes for the explanation
• the cluster cost (Clst) encourages that each graph embedding should at least be close to one prototype of its own class
• the separation cost (Sep) encourages that each graph embedding should stay far away from proto-types not of its class
• diversity of the learned prototypes by adding the diversity loss (Div) which penalizes prototypes too close to each other

ProtGNN: Interpreting Prototypes

AI4BA 2024 - June 26, 2024

• Prototypes are difficult to be interpreted
• We find the most similar subgraph using Monte Carlo Tree Search
• Starting from the initial graph (N₀) as root of the tree, each node is a subgraph obtained from the initial graph by removing nodes or edges

ProtGNN++: Conditional Subgraph Sampling

AI4BA 2024 - June 26, 2024

• As an alternative to MCTS, we assume the explanatory graph is a Gilbert Random Graph (as in PGExplainer) and we conditionally sample it using a NN learning e_ij as
• z_i and z_j are node embedding obtained from the GNN Encoder, which encodes the feature and structure information of the nodes’ neighborhood

ProtGNN++: Accuracy

AI4BA 2024 - June 26, 2024

ProtGNN++: Anecdotal Examples

AI4BA 2024 - June 26, 2024

ProtGNN++: Anecdotal Examples

AI4BA 2024 - June 26, 2024

Encoding Concepts in Graph Neural Networks

Where we show a self-explainable and concept-based GNN XAI method …

AI4BA 2024 - June 26, 2024

AI4BA 2024 - June 26, 2024

Missione 4 • Istruzione e Ricerca 

Missione 4 • Istruzione e Ricerca 

AI4BA 2024 - June 26, 2024

Explainable-by-Design Graph Neural Network

Missione 4 • Istruzione e Ricerca 

Missione 4 • Istruzione e Ricerca 

Highly efficient:

different concepts

AI4BA 2024 - June 26, 2024

Concept Distillation

Missione 4 • Istruzione e Ricerca 

Missione 4 • Istruzione e Ricerca 

AI4BA 2024 - June 26, 2024

Logic Explained Network

Missione 4 • Istruzione e Ricerca 

Missione 4 • Istruzione e Ricerca 

AI4BA 2024 - June 26, 2024

Concept-based Logic Explanation

Missione 4 • Istruzione e Ricerca 

Missione 4 • Istruzione e Ricerca 

AI4BA 2024 - June 26, 2024

Results

Missione 4 • Istruzione e Ricerca 

Missione 4 • Istruzione e Ricerca 

AI4BA 2024 - June 26, 2024

Concept interventions

Counterfactual Explanations

Where we show what if …

AI4BA 2024 - June 26, 2024

Introduction

AI4BA 2024 - June 26, 2024

Explainable Artificial Intelligence?

https://medium.com/@BonsaiAI/what-do-we-want-from-explainable-ai-5ed12cb36c07

AI4BA 2024 - June 26, 2024

Counterfactual Explanation

f( ) = No

Will I have diabetes?

Yes/No + Explanation

f( ) = Yes

Factual

Counterfactual

Explanation: You will not develop diabetes if you lower your fat level and you increase your exercise level.

AI4BA 2024 - June 26, 2024

Generic Counterfactual Explanation

AI4BA 2024 - June 26, 2024

Notation

• Let X ⊆ ℝⁿ be an n-dimensional vector space of real-valued features.
• x = [x₁, x₂, . . . , x_n]^T represents any objects we want to classify as a vector in X.
• Let Y be the output space. Y can either be
• classification → Y = {0, …, K - 1} (K-class classification), or
• Regression → Y ∈ ℝ
• Suppose there exists a predictive model ℎ_𝝎 : X → Y, parameterized by 𝝎, which accurately maps any input feature vector x ∈ X to ℎ_𝝎(x) = 𝑦 ∈ Y.

AI4BA 2024 - June 26, 2024

Counterfactual Explanations for Classification Models

• Given an instance x, a CF x̃ ≠ x according to ℎ_𝝎 is found by perturbing a subset of the features of x, chosen from the set F ⊆ {1, . . . , 𝑛} of features.
• Goal
• When x is replaced by x̃ we must have that ℎ_𝝎(x̃) ≠ ℎ_𝝎(x).
• In the case of classifiers the original predicted class c = ℎ_𝝎(x) is turned into�c̃ = ℎ_𝝎(x̃), such that c ≠ c̃.
• Notice that c̃ can be either
• specified upfront → targeted CF, or
• it can be any c̃ ≠ 𝑐 → untargeted CF.

AI4BA 2024 - June 26, 2024

Counterfactual Explanations for Regression

• Given an instance x, a CF x̃ ≠ x according to ℎ_𝝎 is found by perturbing a subset of the features of x, chosen from the set F ⊆ {1, . . . , 𝑛} of features.
• Goal
• When x is replaced by x̃ we must have that ℎ_𝝎(x̃) ≠ ℎ_𝝎(x).
• In the case of classifiers regressors, instead, the goal is trickier
• One possible approach to specifying the validity of a counterfactual example x̃ is to set a threshold 𝛿 ∈ ℝ \ {0} and let |ℎ_𝝎(x̃) − ℎ_𝝎(x)| ≥ 𝛿.
• However, CFs found via such a thresholding are sensitive to the choice of the threshold 𝛿.

AI4BA 2024 - June 26, 2024

Optimal Counterfactuals

• Amongst all the possible counterfactuals x̃ there exist one that is optimal:
• Minimal perturbation of the original input
• Actionable in terms of possible changes
• More formally, let 𝑔_𝜽: X → X be a counterfactual generator, parameterized by 𝜽, that takes as input x and produces as output a counterfactual example x̃=𝑔_𝜽(x).
• For a given sample D of i.i.d. observations drawn from a probability distribution, i.e., D ∼ 𝑝_data(x), we can measure the cost of generating CFs with 𝑔_𝜽 for all the instances in D, using the following counterfactual loss function:���
• Let F be the set of actionable features only. The goal to find the optimal CF generator 𝑔^*=𝑔_𝜽* where

AI4BA 2024 - June 26, 2024

Picture taken from: https://www.arthur.ai/blog/counterfactual-explainability-neurips

Optimal Counterfactuals

• Amongst all the possible counterfactuals x̃ there exist one that is optimal:
• Minimal perturbation of the original input
• Actionable in terms of possible changes
• More formally, let 𝑔_𝜽: X → X be a counterfactual generator, parameterized by 𝜽, that takes as input x and produces as output a counterfactual example x̃=𝑔_𝜽(x).
• For a given sample D of i.i.d. observations drawn from a probability distribution, i.e., D ∼ 𝑝_data(x), we can measure the cost of generating CFs with 𝑔_𝜽 for all the instances in D, using the following counterfactual loss function:���
• Let F be the set of actionable features only. The goal to find the optimal CF generator 𝑔^*=𝑔_𝜽* where

AI4BA 2024 - June 26, 2024

Metrics for CF Explanations

AI4BA 2024 - June 26, 2024

Metrics

• Validity,
• Proximity,
• Sparsity, and
• Generation Time����

See Sahil Verma, John Dickerson, and Keegan Hines. 2020. Counterfactual Explanations for Machine Learning: A Review. arXiv preprint arXiv:2010.10596 (2020) for a thorough explanation of the metrics

AI4BA 2024 - June 26, 2024

Validity

• It measures the ratio of CFs that actually meet the prediction goal to the total number of CFs generated:
• the higher the validity the better

Validity: 4/9

AI4BA 2024 - June 26, 2024

Proximity

• It is the distance of a CF from the original input sample
• It depends on the distance, usually the smaller the proximity the better

d( , ) = 1/n

AI4BA 2024 - June 26, 2024

Sparsity

• It indicates the number of features that must be changed to get to a given CF
• It is equivalent to the 𝐿₀-norm between a CF and the corresponding original input sample.
• The smaller it is the better, as sparser CFs likely lead to more human-interpretable explanations.

Sparsity( , ) = 1

AI4BA 2024 - June 26, 2024

Generation Time

• It computes the time required to generate CFs
• It should be as small as possible.

AI4BA 2024 - June 26, 2024

Generating Actionable Interpretations from Ensembles of Decision Trees

Tolomei & Silvestri. Generating Actionable Interpretations from Ensembles of Decision Trees. IEEE Transactions on Knowledge and Data Engineering. 2021.

Slides mostly based on:

Tolomei et al. Interpretable predictions of tree-based ensembles via actionable feature tweaking. Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017.��Patent Application:�Tolomei, G., Haines, A., Lalmas, M., & Silvestri, F. (2018). U.S. Patent Application No. 15/444,912.

AI4BA 2024 - June 26, 2024

Predictive Models as Black Boxes

AI4BA 2024 - June 26, 2024

Let’s Open the Black Box

AI4BA 2024 - June 26, 2024

Random Forest Models

AI4BA 2024 - June 26, 2024

Random Forest Models

• “Simple” but very effective especially on Tabular Data
• Used in practice in many applications:
• Advertisement placement
• Ranking
• Recommendation
• ….

AI4BA 2024 - June 26, 2024

… A Bunch of Trees in The Black Box :)

AI4BA 2024 - June 26, 2024

… A Bunch of Trees in The Black Box :)

AI4BA 2024 - June 26, 2024

Preliminaries

• We focus on classification problems.
• Let X ⊆ R_n be an n-dimensional vector space of real-valued features.
• x = [x₁, x₂, . . . , x_n]^T represents any objects we want to classify as a vector in X.
• Each x is associated with a binary class label {-1, +1}.

AI4BA 2024 - June 26, 2024

Preliminaries

• We are given a learnt function f: X→Y that we assume to be represented as an ensemble of K trees: f = ɸ(h₁, h₂, ..., h_K)
• each h_i: X→Y is a base learner estimated on some samples of X.
• We assume the final predicted label is given by a majority voting approach, i.e., ɸ = sign(sum(h_i)).

AI4BA 2024 - June 26, 2024

Problem Definition

AI4BA 2024 - June 26, 2024

𝛿 is a, sort of, proximity value

Positive vs. Negative Paths

AI4BA 2024 - June 26, 2024

Positive vs. Negative Paths

We can skip all the trees containing the positive paths, as these are already encoding the (positive) prediction we ultimately want.

AI4BA 2024 - June 26, 2024

Positive vs. Negative Paths

• We consider the set of positive paths in the tree T.
• We modify a negative instance in order to go through a positive path in T.
• Each feature is modified by at most ε.
• An instance meeting the ε constraint and satisfying the tree is called: ε-satisfactory.

AI4BA 2024 - June 26, 2024

Building ε-satisfactory Instances

• Let us consider a positive path as represented by the conditions from root to leaves


���
• for any (small) fixed ε > 0, we build a positive feature vector x+ dimension-by-dimension as follows:

AI4BA 2024 - June 26, 2024

Finding a Valid Tweaking

• For each positive path in our model we transform our input feature vector x into the ε-satisfactory instance for that path.
• This leads us to a set of tweakings 𝜞_K associated with each tree T_k. The set of all tweakings is then given by 𝜞=⋃ 𝜞_K
• The problem of feature tweaking then becomes that of finding:����
• Solution based on Spatial Indexes for logarithmic-time search

NP-Hard. Reduction to DNF-MAXSAT

AI4BA 2024 - June 26, 2024

Experiments

• Random sample of 1,500 ads out of those served on mobile app by Yahoo Gemini during one month
• 50÷50 positive (high quality) vs. negative (low quality) instances using median dwell time (62.5 secs.) for labelling
• 80÷20 training/test splitting for learning a binary classifier (Decision Tree, GBDT, Random Forest)
• 10-fold cross validation on the training portion to select the best hyper-parameters for each model
• Eventually, the best-performing model on the test set (offline) is Random Forest with 1,000 trees and maximum depth = 16

AI4BA 2024 - June 26, 2024

Ad Quality Experiments

• A use case coming from a real need while working at Yahoo's Gemini Project
• How to suggest advertisers features to modify in order to have their ads being classified as "good-looking"?
• Classifier described in:
• Barbieri, Silvestri, Lalmas: Improving Post-Click User Engagement on Native Ads via Survival Analysis. WWW 2016

AI4BA 2024 - June 26, 2024

Ads Features

AI4BA 2024 - June 26, 2024

Ads Quality Classifiers

AI4BA 2024 - June 26, 2024

Qualitative Evaluation

• We asked a team of creative strategist to evaluate tweakings for 100 randomly selected ads that our classifier scored -1 (Bad Ads). Ratings:
• helpful, non-helpful, or non-actionable
• 57.3% ↦ helpful (inter-agreement: 60.4%)
• 0.4% ↦ non-actionable suggestion.
• about 25% of the 42.3% non-helpful recommendations were considered “neutral”:
• not hurting the user experience if discarded and not adding any positive value.

AI4BA 2024 - June 26, 2024

Feature Importance

AI4BA 2024 - June 26, 2024

Feature Helpfulness (Importance for Actionability)

AI4BA 2024 - June 26, 2024

Impact of ε

AI4BA 2024 - June 26, 2024

Impact of ε on cost 𝛿

• tweaked feature rate:
• proportion of features affected by the transformation of x into x' (range = [0, 1]);
• euclidean distance:
• euclidean distance between x and x' (range = R);
• cosine distance:
• 1 minus the cosine of the angle between x and x' (range = [0, 2]);
• jaccard distance:
• one’s complement of the Jaccard similarity between x and x' (range = [0, 1]);
• pearson correlation distance:
• 1 minus the Pearson’s correlation coefficient between x and x' (range = [0, 2]).

AI4BA 2024 - June 26, 2024

ReLAX: Reinforcement Learning Agent Explainer for Arbitrary Predictive Models

Slides mostly based on:

• Ziheng Chen, Fabrizio Silvestri, Jia Wang, He Zhu, Hongshik Ahn, Gabriele Tolomei: ReLAX: Reinforcement Learning Agent Explainer for Arbitrary Predictive Models. CIKM 2022: 252-261
• Ziheng Chen, Fabrizio Silvestri, Jia Wang, He Zhu, Hongshik Ahn, Gabriele Tolomei: Explain the Explainer: Interpreting Model-Agnostic Counterfactual Explanations of a Deep Reinforcement Learning Agent. IEEE Transactions on Artificial Intelligence

AI4BA 2024 - June 26, 2024

The Idea

0.2

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.2

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

Model

-1

AI4BA 2024 - June 26, 2024

The Idea

0.2

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.2

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.7

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.7

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

Model

AI4BA 2024 - June 26, 2024

The Idea

Model

-1

AI4BA 2024 - June 26, 2024

The Idea

0.7

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.7

blue

20

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.7

blue

5

red

Model

AI4BA 2024 - June 26, 2024

The Idea

0.7

blue

5

red

Model

AI4BA 2024 - June 26, 2024

The Idea

Model

AI4BA 2024 - June 26, 2024

The Idea

Model

+1

AI4BA 2024 - June 26, 2024

The Counterfactual x̃

AI4BA 2024 - June 26, 2024

Markov Decision Process Formulation

• M = {S, A, T , p₀, r, γ}
• States
• Actions
• reward
• States ≡ intermediate “counterfactual samples”
• Also keeps track of which features have been modified
• Actions ≡ Discrete-Continuous Hybrid Actions
• which feature, what change.
• Reward
• we make a trade-off between achieving the counterfactual prediction goal and the distance of the counterfactual from the original input sample x
• We adopt a Policy Optimization strategy to find the policy that can be used to select the sequence of actions to perform on x.

AI4BA 2024 - June 26, 2024

Overview of our proposed ReLAX framework

AI4BA 2024 - June 26, 2024

Who Explains the Explainer

• The complex network structure of a DRL policy learned for CF generation poses a challenge for understanding and reasoning about the decision logic of the agent.
• To explain the decision process of a learned policy, we distill knowledge from the policy to a much smaller decision tree (DT).

AI4BA 2024 - June 26, 2024

Experiments: The Datasets

AI4BA 2024 - June 26, 2024

Experiments: The (Black Box) Model Used

AI4BA 2024 - June 26, 2024

Experiments Sparsity vs. Validity

AI4BA 2024 - June 26, 2024

Validity measures the ratio of CFs that actually meet the prediction goal to the total number of CFs generated.

Sparsity measures the number of features changed

Sparsity vs. Validity: The Case of Boston Housing

As this is a regression task we rely on the concept of validity threshold 𝛿 (|ℎ_𝝎(x̃) − ℎ_𝝎(x)| ≥ 𝛿). The higher 𝛿 the more difficult for the model to find a valid CF example

AI4BA 2024 - June 26, 2024

Proximity and Generation Time

AI4BA 2024 - June 26, 2024

Impact of the “Black Box”

AI4BA 2024 - June 26, 2024

Effect of λ (The Importance of Proximity)

AI4BA 2024 - June 26, 2024

A Case Study: COVID19 Mortality

AI4BA 2024 - June 26, 2024

Graph Convolutional Neural Networks

AI4BA 2024 - June 26, 2024

Why Convolutional

• They update each node by aggregating information from nearby nodes.
• As such, they induce a relational inductive bias (i.e., a bias toward prioritizing information from neighbors).
• They are spatial-based because they use the original graph structure.
• This contrasts with spectral-based methods, which apply convolutions in the Fourier domain.
• Each layer of the GCN is a function F[•] with parameters Φ that takes the node
• embeddings and adjacency matrix and outputs new node embeddings.

• X is the input
• A is the adjacency matrix
• H_k is the k-th layer node embedding
• ϕ_k denotes the parameters that map from layer k to layer k+1

AI4BA 2024 - June 26, 2024

Example GCN Layer

• At each node n in layer k, we aggregate information from neighboring nodes by summing their node embeddings h_•:���
• Then we apply a linear transformation Ω_k to the embedding h_k⁽ⁿ⁾ at the current node and to this aggregated value, add a bias term β_k, and pass the result through a nonlinear activation function a[•].�
• All in all

ne[n] == neighbors of node n

AI4BA 2024 - June 26, 2024

Example GCN Layer

• More succinctly, if we collect the node embeddings into the D×N matrix H_k and post-multiply by the adjacency matrix A, the nth column of the result is agg[n, k].
• The update for the nodes is now:������
• where 1 is an N×1 vector containing ones.
• Here, the nonlinear activation function a[•] is applied independently to every member of its matrix argument.

AI4BA 2024 - June 26, 2024

Example: Graph Classification with GCN

• The network inputs are the adjacency matrix and node embedding matrix X.
• The adjacency matrix A ∈ R^N×N derives from the molecular structure.
• The columns of the node embedding matrix X ∈ R^118×N are one-hot vectors indicating which of the 118 elements of the periodic table are present.
• In other words, they are vectors of length 118 where every position is zero except for the position corresponding to the relevant element, which is set to one.
• The node embeddings can be transformed to an arbitrary size D by the first weight matrix Ω₀ ∈ R^D×118

AI4BA 2024 - June 26, 2024

Example: Graph Classification with GCN

• The network inputs are the adjacency matrix and node embedding matrix X.
• The adjacency matrix A ∈ R^N×N derives from the molecular structure.
• The columns of the node embedding matrix X ∈ R^118×N are one-hot vectors indicating which of the 118 elements of the periodic table are present.
• In other words, they are vectors of length 118 where every position is zero except for the position corresponding to the relevant element, which is set to one.
• The node embeddings can be transformed to an arbitrary size D by the first weight matrix Ω₀ ∈ R^D×118

AI4BA 2024 - June 26, 2024

CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks

Slides mostly based on:

• Ana Lucic, Maartje A. ter Hoeve, Gabriele Tolomei, Maarten de Rijke, Fabrizio Silvestri: CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks. AISTATS 2022: 4499-4511

AI4BA 2024 - June 26, 2024

Graph Neural Networks for Node Classification

Curtesy of http://snap.stanford.edu/proj/embeddings-www/files/nrltutorial-part2-gnns.pdf

AI4BA 2024 - June 26, 2024

CF-Example for Graph NNs

• A CF example x* for an instance x according to a trained classifier f is found by perturbing the features of x such that f(x*) != f(x)
• An optimal CF example x^o is one that minimizes the distance between the original instance and the CF example, according to some distance function d, and the resulting optimal CF explanation is ∆x^o = x* − x
• For graph data, it may not be enough to simply perturb node features, especially since they are not always available.

AI4BA 2024 - June 26, 2024

Counterfactual Explanations for Node Prediction

• The goal is to find the smallest subgraph that if removed the model will predict a different class for a node.

Matrix sparsification

original

Counterfactual model

AI4BA 2024 - June 26, 2024

Adjacency Matrix Perturbation

• For a node v, we consider G_v=(A_v, X_v)
• A_v is the restriction of A (the adjacency matrix) to the l-hop neighborhood of v (X_v) is the corresponding edge set.
• A_v* = P ⊙ A_v
• P is a perturbation matrix
• To generate P we first generate an intermediate real-valued P* which we threshold in order to get P*

AI4BA 2024 - June 26, 2024

An example for GCN

• We start from the traditional GCN formulation��
• We modify it to explicitly isolate A_v��
• We define a new model g depending on P

AI4BA 2024 - June 26, 2024

CF-GNNExplainer

AI4BA 2024 - June 26, 2024

Experiments

• Baselines:
• RANDOM
• 1-HOP
• All edges in the ego-graph
• RM-1HOP
• All edges *not* in the ego-graph
• (Modified) GNNExplainer
• Metrics
• Fidelity
• Explanation Size
• Sparsity
• Accuracy

AI4BA 2024 - June 26, 2024

Datasets

• TREE-CYCLES
• binary tree (base graph), with cycle-shaped motifs
• TREE-GRIDS
• binary tree, with 3×3 grids as the motifs
• BA-SHAPES
• Barabasi-Albert (BA) with house-shaped motifs, where each motif consists of 5 nodes (one for the top of the house, two in the middle, and two on the bottom).
• Task:
• Node classification. Classes: not-in-motif, in-motif: top, middle, bottom.
• Baseline Model (f) we want to explain:
• 3-layer GCN (hidden size = 20) for each task.
• Our GCNs have at least 87% accuracy on the test set.

AI4BA 2024 - June 26, 2024

Datasets Statistics

AI4BA 2024 - June 26, 2024

Experiments: Metrics

• Fidelity: the proportion of nodes where the original predictions match the prediction for the explanations
• Explanation Size: is the number of removed edges.
• the difference between the original A_v and the counterfactual A̅_v.
• Since we want to have minimal explanations, we want a small value for this metric
• Accuracy: Validity
• Sparsity

AI4BA 2024 - June 26, 2024

Experiments: Results

AI4BA 2024 - June 26, 2024

Experiments: Explanation Size

AI4BA 2024 - June 26, 2024

Experiments: Explanation Size

AI4BA 2024 - June 26, 2024

GNNExplainer (Not Counterfactual)

AI4BA 2024 - June 26, 2024

GNNExplainer (Not Counterfactual)

GNNEXPLAINER generates an explanation by identifying a small subgraph of the input graph together with a small subset of node features (shown on the right) that are most influential for ŷ_i. Examining explanation for ŷ_i, we see that many friends in one part of v_i’s social circle enjoy ball games, and so the GNN predicts that v_i will like basketball. Similarly, examining explanation for ŷ_j , we see that v_j’s friends and friends of his friends enjoy water and beach sports, and so the GNN predicts ŷ_j = “Sailing.”

AI4BA 2024 - June 26, 2024

Experiments: Against GNNExplainer

• GNNExplainer cannot find S automatically, so we try varying values of S. GT indicates the size of the ground truth explanation for each dataset.
• CFGNNExplainer finds S automatically.

AI4BA 2024 - June 26, 2024

More Information on Counterfactual GNN Explainers

AI4BA 2024 - June 26, 2024

More Information on Counterfactual GNN Explainers

AI4BA 2024 - June 26, 2024

All Good Things Must Come To An End

AI4BA 2024 - June 26, 2024

One Last Thing

Where we show that XAI can even be used adversarially …

AI4BA 2024 - June 26, 2024

The Impact of Source-Target Node Distance on Vicious Adversarial Attacks in Social Network Recommendation Systems

Giovanni Trappolini, Federico Albanese, Lorenzo Scarlitti, Fabrizio Silvestri

OUTLINE

• How to “mount” the attack [1]

​

• The impact of node distance

​

​

​

[1] Trappolini, G., Maiorca, V., Severino, S., Rodola, E., Silvestri, F., & Tolomei, G. (2023). Sparse vicious attacks on graph neural networks. IEEE Transactions on Artificial Intelligence. https://ieeexplore.ieee.org/abstract/document/10264111

AI4BA 2024 - June 26, 2024

GOAL

Adversarial Attacks → on what?

AI4BA 2024 - June 26, 2024

TASK: LINK PREDICTION

AI4BA 2024 - June 26, 2024

TASK: LINK PREDICTION

AI4BA 2024 - June 26, 2024

TASK: LINK PREDICTION

A malicious node “s” attacks target user “t”

AI4BA 2024 - June 26, 2024

BEFORE…

Before analyzing how we mount this attack we’ll analyze some common “pitfalls” in the state of the art.

AI4BA 2024 - June 26, 2024

CHOICE OF USERS

Some methods assume the attacker can control a subset of the users of the network that already exist.

AI4BA 2024 - June 26, 2024

VICIOUS USERS

AI4BA 2024 - June 26, 2024

VICIOUS USERS

Disproportionate use of vicious nodes, Budgeted

AI4BA 2024 - June 26, 2024

BACKGROUND

2 Steps:

​

1. GCN (see image)
2. MLP

AI4BA 2024 - June 26, 2024

PROPOSED METHOD

Sparse Attacks: we employ a significant smaller number of malicious users to mount the attack → akin to sparse regression

AI4BA 2024 - June 26, 2024

HOW?

To achieve this we use a set of 3 losses:

1. For the adversarial attack itself.
2. To reduce the number of actions.
3. To reduce the numbers of malicious users.

AI4BA 2024 - June 26, 2024

HOW?

AI4BA 2024 - June 26, 2024

1.

I.e. the attack must be successful, the link prediction systems must detect the link.

AI4BA 2024 - June 26, 2024

2.

AI4BA 2024 - June 26, 2024

2.

AI4BA 2024 - June 26, 2024

RESULTS (I)

AI4BA 2024 - June 26, 2024

IMPORTANT OPEN PROBLEMS

1. How does it perform in “real” scenarios/datasets.

AI4BA 2024 - June 26, 2024

IMPORTANT OPEN PROBLEMS

• How does it perform in “real” scenarios/datasets.
• How does distance impact the results?

AI4BA 2024 - June 26, 2024

RESULTS - Effectiveness

AI4BA 2024 - June 26, 2024

RESULTS - Efficiency

AI4BA 2024 - June 26, 2024

This is The End

AI4BA 2024 - June 26, 2024