Skip to content

Pruning Methods

Pruning can be used as a post-processing feature to reduce the size of the contrastive explanation graph. For complex problems the size of the explanation graph can grow to a level where interpretation can be difficult. For cases like this pruning can be useful to remove parts of the explanation that are unrelated or not necessary. The applicability and usfulness of the different pruning approaches vary for different programs.

Pruning Methods

Orphans

This pruning method removes all orphan subgraphs that are not connected to the main subgraph which contains the query and changed nodes. It is useful for removing parts of the contrastive graph that are not directly connected to main explanation.

asplain [...] --prune ORPHANS
orphans.lp

Encoding

#include "./change.lp".

Always include query

node_included(N,T) :- query(N, _), node(N,T).

Always include changes

node_included(N,T) :- change(_, N), node(N,T).
node_included(N2,T) :- node_included(N1,_), node(N2,T), edge((N1,N2), _).
node_included(N2,T) :- node_included(N1,_), node(N2,T), edge((N2,N1), _).
edge_included((N1,N2),T) :- edge((N1,N2),T), node_included(N1,_), node_included(N2,_).

change.lp

Encoding

change(rm,N)  :- node(N,_), program(N, ref), not program(N, foil), solved(foil).
change(add,N) :- node(N,_), program(N, foil), not program(N, ref), solved(foil).

Paths

This pruning method finds paths over the contrastive graph edges connecting the query and changed nodes. Only the nodes forming these paths are included after the pruning, since these are the nodes directly connecting the main elements of the explanation.

asplain [...] --prune PATHS
paths.lp

Encoding

#include "./change.lp".

EXTERNAL: path_depth(N). Always include query with distance 0

reachable_query(N,T) :- query(N, _), node(N,T).

Always include changes with distance 0

reachable_change(N,T) :- change(_, N), node(N,T).
reachable_query(M,T) :- edge((N,M),_), node(M,T), reachable_query(N,_).
reachable_change(M,T) :- edge((N,M),_), node(M,T), reachable_change(N,_).

FIND INTERSECTIONS

intersection(N,T) :- reachable_query(N,T), reachable_change(N,T).
reachable_query_back(N,T) :- intersection(N,T).
reachable_change_back(N,T) :- intersection(N,T).

BACK DIRECTION

reachable_query_back(N,T) :- edge((N,M),_), node(N,T), reachable_query_back(M,_).
reachable_change_back(N,T) :- edge((N,M),_), node(N,T), reachable_change_back(M,_).

PATH INCLUSIONS

node_path(N,T) :- reachable_query(N,T), reachable_query_back(N,T).
node_path(N,T) :- reachable_change(N,T), reachable_change_back(N,T).

DEPTH

node_path_depth(N,T,0) :- node_path(N,T).
node_path_depth(M,T,D+1) :- node_path_depth(N,_,D), edge((N,M),_), node(M,T), path_depth(DMAX), D < DMAX.
node_path_depth(M,T,D+1) :- node_path_depth(N,_,D), edge((M,N),_), node(M,T), path_depth(DMAX), D < DMAX.

INCLUDED

node_included(N,T) :- node_path_depth(N,T,D).
edge_included((N1,N2),T) :- edge((N1,N2),T), node_included(N1,_), node_included(N2,_).

change.lp

Encoding

change(rm,N)  :- node(N,_), program(N, ref), not program(N, foil), solved(foil).
change(add,N) :- node(N,_), program(N, foil), not program(N, ref), solved(foil).

Changes

This pruning method only keeps the nodes that changed between the reference program and the found foil. This method is especially useful for really large graphs where only focusing on the changed nodes can provide a clearer explanation.

Warning

When the query is already satisfied in the reference model, this pruning method will not keep any nodes since there are no changes between the reference and the foil.

asplain [...] --prune CHANGES
changes.lp

Encoding

#include "./change.lp".

Always include query

node_included(N,T) :- query(N, _), node(N,T).

Always include changes

node_included(N,T) :- change(_, N), node(N,T).
node_included(N,T) :- fired(N), node(N,T).
node_included(N,T) :- node(N, T), model(N, ref), not model(N, foil).
node_included(N,T) :- node(N, T), model(N, foil), not model(N, ref).
edge_included((N1,N2),T) :- edge((N1,N2),T), node_included(N1,_), node_included(N2,_).

change.lp

Encoding

change(rm,N)  :- node(N,_), program(N, ref), not program(N, foil), solved(foil).
change(add,N) :- node(N,_), program(N, foil), not program(N, ref), solved(foil).