11institutetext:  Department of Mathematics and Geosciences, University of
Trieste, Trieste, Italy
11email<EMAIL_ADDRESS>22institutetext: Department of
Economics, Business, Mathematics and Statistics, University of Trieste, Italy
22email<EMAIL_ADDRESS>33institutetext: LMU Munich, Munich,
Germany 44institutetext: Munich Center for Machine Learning (MCML), Munich,
Germany
44email<EMAIL_ADDRESS>55institutetext: Department of Engineering and
Architecture, University of Trieste, Trieste, Italy
55email<EMAIL_ADDRESS>
# Decision Predicate Graphs: Enhancing Interpretability in Tree Ensembles

Leonardo Arrighi 11 0009-0006-2494-0349 Luca Pennella 22 0009-0006-2721-1248
Gabriel Marques Tavares 33 4 4 0000-0002-2601-8108 Sylvio Barbon Junior 55
0000-0002-4988-0702

###### Abstract

Understanding the decisions of tree-based ensembles and their relationships is
pivotal for machine learning model interpretation. Recent attempts to mitigate
the human-in-the-loop interpretation challenge have explored the extraction of
the decision structure underlying the model taking advantage of graph
simplification and path emphasis. However, while these efforts enhance the
visualisation experience, they may either result in a visually complex
representation or compromise the interpretability of the original ensemble
model. In addressing this challenge, especially in complex scenarios, we
introduce the Decision Predicate Graph (DPG) as a model-agnostic tool to
provide a global interpretation of the model. DPG is a graph structure that
captures the tree-based ensemble model and learned dataset details, preserving
the relations among features, logical decisions, and predictions towards
emphasising insightful points. Leveraging well-known graph theory concepts,
such as the notions of centrality and community, DPG offers additional
quantitative insights into the model, complementing visualisation techniques,
expanding the problem space descriptions, and offering diverse possibilities
for extensions. Empirical experiments demonstrate the potential of DPG in
addressing traditional benchmarks and complex classification scenarios.

###### Keywords:

Ensemble Learning Explainable Artificial Intelligence Interpretability
Explainability Tree-based Ensemble Method Graph Random Forest

##  1 Introduction

Artificial intelligence, although still under strong development, is now a
consolidated and widely used tool. This is thanks to the continuous growth of
computing power, which allows the use of increasingly complex and
computationally expensive machine learning (ML) methods. The challenges
presented by modern-world problems are growing in complexity as well as the
proposed solutions.

Dealing with large quantities of data and frequently encountering unbalanced
datasets are still significant obstacles in addressing many real-world issues;
however, tree-based ensemble algorithms offer several advantages in overcoming
these challenges, including robustness to noise and outliers, scalability to
large datasets, automatic handling of missing values, and the ability to
capture complex relationships and interactions within the data [1, 2].

Without delving into the intricacies of various algorithms, exhaustively
described by Hastie et al. [3], the process of learning tree-based ensemble
models involves training multiple decision trees to combine their predictions,
optimising performance, and enhancing generalisation capabilities. While these
models indeed offer concrete solutions to a diverse array of problems,
developers and users are confronted with new challenges. The training outcome
yields an exceptionally complex model, commonly referred to as an opaque-box
model (also known as the black-box problem), whose internal workings are not
transparent or easily interpretable [4]. In response to this context, the
Decision Predicate Graph (DPG) is proposed in this paper.

Drawing inspiration from the expanding theme of eXplainable Artificial
Intelligence (XAI), we designed a graph structure to tackle transparency and
explainability challenges inherent in tree-based ensemble models. This
facilitates a better understanding of the intricate choices underlying these
ML models. DPG is created with inspiration from the concept of aggregating
random forests (RF) [5, 6], as introduced by Gossen and Steffen [7]. The
approach proposed in [7] suggests visualising the decisions within the RF by
combining the branches of the tree base learners into a single and compact
decision diagram. The concept behind DPG is to convert a generic tree-based
ensemble model for classification into a graph, a defined and studied
structure with known properties. In this graph, nodes represent predicates,
i.e., the feature-value associations present in each node of every tree, while
edges denote the frequency with which these predicates are satisfied during
the model training phase by the samples of the dataset. The DPG structure
enables comprehending the choices made by the model, enhancing transparency
and understandability. Moreover, it allows the exploitation of graph
properties to develop metrics and algorithms facilitating the analysis of the
ensemble model. This, in turn, aids in understanding the decisions it makes,
easing the task of visualising the graph which can be vast and complicated for
larger models with numerous tree base learners.

DPG serves as a model-agnostic tool offering a comprehensive interpretation of
tree-based ensemble models. It provides descriptive metrics that enhance the
understanding of the decisions inherent in the model, offering valuable
insights. This tool proves particularly useful for models that are _a priori_
considered satisfactory in terms of performance.

Our work contributes in the following ways:

  * •

we introduce DPG, a novel interpretability structure that transforms an
opaque-box tree-based ensemble model into an enriched graph;

  * •

we present the algorithm used to create DPG, accompanied by pseudo-code to
enhance understanding and facilitate replication, complete with its asymptotic
complexity;

  * •

we provide the interpretation of three metrics from graph theory, enriching
the model comprehension and gaining insights;

  * •

we demonstrate the use of the proposed method through two case studies: the
application of DPG to two RF models, respectively, on the Iris dataset [8] and
a challenging dataset.

It is important to highlight that these results are achieved in a generic
fashion, utilising a standard classifier on well-established datasets.
Significantly, we intentionally avoided incorporating scenario-specific
heuristics. Therefore, we posit that our aggregation approach has the
potential for widespread application across a diverse range of related
scenarios.

##  2 Literature Review

Complex yet effective models have become increasingly prevalent, especially in
fields where the outcomes bear significant importance and require a heightened
level of sensitivity. In these scenarios, there is a growing demand for models
to exhibit transparency, accountability, and a comprehensive understanding.
Consequently, the discussion on XAI has experienced significant growth,
leading to an extensive body of literature [9, 10, 11].

In XAI, as suggested by Dwivedi et al. [12], classifications are often based
on scope, distinguishing between global interpretability, which reveals
overall data trends and provides insights into the entire model, and local
interpretability, which elucidates the reasoning behind specific predictions
for individual instances. Another classification criterion involves how
interpretability is achieved: intrinsic interpretability relies on
straightforward model structures (e.g., concise decision trees or linear
models), while post hoc interpretability involves methods applied after model
training [11]. Interpretation methods are further categorised as model-
specific or model-agnostic. Model-specific interpretation tools are tailored
to specific model classes, limiting their applicability. In contrast, model-
agnostic tools are versatile, capable of being employed with any ML model, and
are applied post-training (e.g., SHAP [13], LIME [14], PDP [15], and Anchors
[16]).

In this context, XAI tools, especially those providing global interpretations,
become valuable instruments for understanding tree-based ensemble models.
These models are widely used in addressing diverse problem domains, as
highlighted in several surveys [17, 18, 19]. As a result, the number of
studies delving into model-specific techniques tailored for ensembles of trees
has also increased.

The first significant study is proposed by Mashayekhi and Gras [20]. The
authors introduced _RF+HC_ , an approach that employs a hill climbing
algorithm in RF to search for a decision set. This rule set reduces the number
of decisions dramatically, which significantly improves the comprehensibility
of the underlying model built by RF. Similarly, Hara and Hayashi [21] exploits
Bayesian model selection to extract the decision set. These approaches share
similarities with our method; however, our proposal extends beyond the
extraction of decisions from the RF. Visualising the decisions of tree-based
ensemble models and simultaneously complementing them with metrics developed
by graph theory makes DPG more adaptable and holistic. This approach allows
for obtaining insights into the model beyond just decision information.

Zhao et al. [22] proposed _iForest_ , a visual analysis system specifically
designed to interpret RF models and their predictions. They built a feature
view to illustrate the relationships between input features and outcome
predictions and proposed a design that summarises multiple decision paths
based on feature occurrences and ranges, allowing users to explore and
understand the partitioning logic of these paths. The iForest, like numerous
visualisation systems, faces significant challenges related to scalability and
interpretability when dealing with large ensembles. To overcome this
challenge, our approach does not prioritise visualisation but instead strives
for a comprehensive understanding of the ensemble’s logic.

Hatwell et al. [23] contributed with _Collection of High Importance Random
Path Snippets_ (CHIRPS), a method that incorporates the explanation of RF
classification for each data instance and extracts a decision path from each
tree in the forest, resulting in a set of decisions that elucidate the
classification process. However, this method is limited to rules extraction
and lacks insight into the model’s structure. Additionally, it does not
incorporate metrics to explain the logic of the tree-based ensemble model.

Another technique focused on visualising decisions underlying RF models is
introduced by Neto and Paulovich [24]. _Explainable Matrix_ (ExMatrix) employs
a matrix-like visual metaphor, where rows represent decisions, columns denote
features, and cells encapsulate decision predicates, thereby facilitating the
scrutiny of models and the audit of classification outcomes. The visualisation
capability of ExMatrix for global visualisation has limitations in terms of
scalability because the number of decisions increases significantly with the
number of trees in large ensembles. Moreover, ExMatrix layouts can rapidly
become challenging to explore, while the complexity of the model increases. As
mentioned earlier, our approach enables us to retrieve information without
relying solely on visualisation.

Dedja et al. [25] introduced an approach denoted as _Building Explanations
through a LocalLy AccuraTe Rule EXtractor_ (BELLATREX), which is designed to
explain the forest predictions for a given test instance by a set of logical
rules based on the features of the dataset. However, a potential limitation
lies in the computational complexity of the approach. While explaining a
single prediction is quick, applying the method to a complete dataset becomes
computationally expensive. Furthermore, BELLATREX focuses on instance-level
explanations rather than providing a global perspective. In addition,
BELLATREX uses clustering techniques to simplify the representation and
decision logic, whereas our approach uses graphs to avoid simplifications that
can lead to loss of information.

Various studies [26, 27, 28, 29] proposed several tree similarity metrics
through the process of clustering based on tree representations. However,
these approaches, while beneficial for interpretability, require simplifying
the model through techniques such as selection, pruning, and frequency
analysis, which can result in information loss.

A number of works [30, 31, 7, 32] established a connection between tree-based
ensemble models and graph theory. The foundational concept of these techniques
has been explored by [33, 34, 35, 36, 37, 38, 39]. These works established the
theory that introduces the transformation of decision trees into graphs,
aiming for more efficient and non-redundant tree structures. Nakahara et al.
[30] and Silva et al. [31] works focus on performance optimisation, with
Gossen and Steffen [7] and Murtovi et al. [32] being the sole contributors
that employed these techniques for interpretability purposes.

In particular, Gossen and Steffen [7] introduced the _Algebraic Decision
Diagram_ (ADD), aiming to transform tree-based ensemble models into bipartite
graphs. The ADD serves as an alternative construction to RF, providing an
additional predictive model that functions as a surrogate. ADD proves valuable
for specific aspects of interpretability, such as outcome explanation, logic
of _majority vote_ , and visualising the path. Acting as a surrogate model,
their primary contributions lie in the ability to provide a simple, optimised
model. In comparison, our objective is to extend their ideas by fully
leveraging graph theory. This goes beyond the transposition of tree-based
ensemble models into a graph; rather, it involves using graph theory and its
associated metrics to gain insights into the functionality of the models.

_ForestGUMP_ , an online tool developed by Murtovi et al. [32], is designed
for generating ADDs. This tool provides valuable information such as graph
visualisation, hypothetical sample path display, and logic of majority vote.
However, it has some limitations in terms of the number of usable trees (only
$20$) and in visualising problems that involve multiple features and
classification choices, making graph navigation complex. In our work, while we
enable visualisation, our focus is on utilising graph-related metrics, and we
do not incorporate the simplification of the analysed models.

##  3 Decision Predicate Graphs

DPGs capture the details of a tree-based ensemble model and learned dataset
specifics, emphasising predicate paths while preserving crucial decision
points. Essentially, DPG converts complex ensemble models into a graph
structure, where nodes represent predicates made by the model and edges denote
the occurrence of these predicates during model training.

In this segment, we present the formalisation of DPG, elucidate the algorithm
employed in its development through pseudo-code and its asymptotic complexity,
and provide a detailed exposition of various metrics and properties essential
for comprehending the tree-based ensemble model. Moreover, we meticulously
outline the advantages of metrics and articulate why they can serve as a
valuable complementary aid to graph visualisation, particularly in overcoming
its inherent limitations.

As previously mentioned in Section 1, DPG is tailored for tree-based ensemble
models designed specifically for classification tasks.

###  3.1 Definition

Let $\mathcal{M}_{n}$ be the tree-based ensemble model consisting of $n$ tree
base learners $T(x;\Theta_{b})$, where $x$ is a generic sample, and
$\Theta_{b}$ characterizes the $b$th learner in terms of split variables,
cutpoints at each node, and terminal-node values. More specifically,
$\Theta_{b}$ includes:

  * •

all the splitting conditions associated with each $j$th internal node $n_{bj}$
based on a specific feature $f_{bj}$ and a threshold (for numerical features)
or a set of possible values (for categorical features) $t_{bj}$;

  * •

the values assigned to leaf nodes $c_{b}$.

Let $\mathcal{D}$ be the training set on which $\mathcal{M}_{n}$ is trained.
Every base learner is trained on a dataset $\mathcal{D}_{b}$, where
$\mathcal{D}_{b}$ is a subset of $\mathcal{D}$. We define $\mathcal{O}$ as the
set of logical operations: $\mathcal{O}=\\{\leq,>,=,\neq\\}$.

A predicate set $\mathcal{P}(\mathcal{M}_{n})$, for an ensemble method
$\mathcal{M}_{n}$ is the set obtained by the union of the set of all the
triples $p=(f_{bj},o,t_{bj})$, where $o\in\mathcal{O}$, and $f_{bj}$,
$t_{bj}\in\Theta_{b}$, and the set of all leaf nodes $c_{b}$, for all $n$ tree
base learners of $\mathcal{M}_{n}$. The triples $p$ are called decisions,
while the elements of $\mathcal{P}(\mathcal{M}_{n})$ are called predicates.

A Decision Predicate Graph (DPG$(\mathcal{M}_{n})$) for a model
$\mathcal{M}_{n}$ is a directed weighted graph $(\mathcal{P},E)$ where:

  * •

$\mathcal{P}$ is the set of nodes, which corresponds to the predicate set
$\mathcal{P}(\mathcal{M}_{n})$;

  * •

$E$ is the set of edges, where each edge represents the frequency with which a
sample consecutively satisfies two predicates in a given base learner. This
frequency is computed considering all the samples of the training set
$\mathcal{D}$ for each base learner.

For conciseness, from this point onward, we will use the acronym DPG to refer
to the graph, indicating that it is constructed based on a model.

###  3.2 From Ensemble to a DPG

We introduce an algorithm, outlined in Algorithm 1, for constructing the DPG
based on a tree-based ensemble model, by traversing all tree base learners
with the training samples.

1

Input: Ensemble tree model $\mathcal{M}_{n}$, Training set $\mathcal{D}$

Output: DPG$(\mathcal{M}_{n})$

2

3Initialise empty set DPG$(\mathcal{M}_{n})$;

4

5foreach  _$T$ (learner) in $\mathcal{M}_{n}$_ do

6

7 Initialise empty predicate set $\mathcal{P}$ and edge set ${E}$;

8

9 foreach  _$x$ (sample) in $\mathcal{D}$_ do

10 Initialise empty predicate set $\mathcal{P}_{x}$ and edge set ${E_{x}}$;

// To obtain the predicates path for $x$ on the tree $T$

11 ($\mathcal{P}_{x}$, ${E_{x}}$) $\leftarrow$ TRAVERSING(_$T,x$_);

12 Add ($\mathcal{P}_{x}$, ${E_{x}}$) to $\mathcal{P}$ and ${E}$;

13

14

15

16DPG$(\mathcal{M}_{n})$ $\leftarrow$ AGGREGATING(_( $\mathcal{P}$, ${E}$)_);

17

18return _DPG $(\mathcal{M}_{n})$_;

Algorithm 1 Construct DPG from Ensemble Tree Model

The algorithm iterates over each base learner in the ensemble tree model
$\mathcal{M}_{n}$ and each training sample $x$ in the training set
$\mathcal{D}$.

To clarify, the TRAVERSING function follows the predicate path of a particular
input sample $x$ through the decision tree $T$, starting from the root node
and navigating to the appropriate leaf node based on the feature values of
$x$. Meanwhile, the AGGREGATING function processes the predicates and edges
obtained from TRAVERSING the decision trees for all samples into a single
graph representation, DPG$(\mathcal{M}_{n})$, by taking the union of
$\mathcal{P}$ and computing the frequency of elements of $E$.

The algorithm presents a systematic methodology for constructing DPG. The
overall asymptotic complexity can be formally expressed as follows:

$O(b\times s\times(k+k^{2}))=O(b\times s\times k^{2})$

where:

  * •

$b$ is the number of learners in the ensemble,

  * •

$s$ is the number of samples in the training set, $|\mathcal{D}|$, and

  * •

$k$ represents the size of the ($\mathcal{P}_{x}$, ${E_{x}}$) processed by the
TRAVERSING and AGGREGATING functions.

This analysis takes into account the linear time complexity $O(k)$ for the
TRAVERSING function and the quadratic time complexity $O(k^{2})$ for the
AGGREGATING function. Our _Python_ 3.10 implementation is accessible
here111https://github.com/sbarbonjr/fhg/tree/main.

###  3.3 DPG interpretability

In this section, we enumerate and elucidate some of the advantages that DPG
can offer. The graph-based nature of DPG provides significant enhancements in
the direction of a complete mapping of the ensemble structure. Weighted
directed graphs, such as DPGs, are studied structures with well-established
properties that enable the identification or construction of useful metrics
and algorithms. It is crucial to emphasise that all the observations presented
in this section are valuable for comprehending and analysing the obtained
model.

####  3.3.1 Visualisation.

DPG provides an immediate advantage by allowing the visualisation of the
entire tree-based ensemble models through a single comprehensive graph.
Similar to the idea proposed by Gossen and Steffen [7], consolidating all
individual basic learners within the model into a unified graph provides a
holistic representation of the decision-making process. This visualisation not
only elucidates the decisions made by the learners but also reveals the
intricate relationships between them. Consequently, it facilitates a
comprehensive understanding of the utilised features and, more importantly,
the associations between features and their values that enable the model to
accurately classify a sample into a specific class.

Another noteworthy aspect of DPG lies in the concept of representing edges as
frequencies. This feature enables a discerning analysis of the most
significant path through predicates, shedding light on decisions consistently
employed by numerous learners or across multiple samples. This insight not
only highlights the prevalence of certain decisions but also opens avenues for
targeted enhancement strategies, focusing on those influential aspects within
the model.

Moreover, by traversing all the possible paths between predicates in reverse,
starting from one of the classes, we can discern the essential characteristics
that a sample must possess to be classified into a specific class. This
capability facilitates the _a priori_ elimination of certain elements from the
dataset when considering the particular class.

Nevertheless, we acknowledge that while visualisation is a valuable tool, its
effectiveness diminishes with an increasing number of tree base learners. A
multitude of tree base learners implies an increase in decisions and,
consequently, an abundance of predicates. As a result, the size of the graph,
in terms of nodes, grows proportionally with the model’s scale. This expansion
can render the graph illegible or impractical to visualise due to its
intricate complexity. To address this challenge, we provide additional tools
that complement the visualisation, aiding in the extraction of model
properties and facilitating a more comprehensible understanding.

One approach is based on the desire and feasibility of determining the
specific characteristics a sample must exhibit to be assigned to a particular
class. Taking inspiration from the _outcome explanation problem_ introduced by
Gossen and Steffen [7], to enhance the immediacy and effectiveness of this
analysis, we provide an aggregation of predicates, referred to as _constraint_
, which represent intervals associated with the features of each class. The
constraints are defined as follows: for a given class identified in the DPG,
we list all nodes connected by a path originating from the node itself and
culminating in the class. For each feature within the node predicates, we
delineate the most extensive possible interval using the values associated
with the features. This interval is defined by two endpoints. The minor
endpoint is the smallest value within the set of values less than the feature,
while the major endpoint is the largest value within the set of values greater
than the feature. If either of these two sets is empty, the interval is deemed
infinite. Each class has its constraints for every feature contributing to the
classification of the samples.

####  3.3.2 Centrality.

The centrality of a node is defined as a number or rank corresponding to the
node position within the network. By observing centrality, we can make
considerations that allow us to better understand the process hidden in the
ensemble method. The notion of centrality encompasses a wide range of metrics.
In this section, we explore those metrics that offer the most insightful
information.

According to Brandes [40], we define the _betweenness centrality_ (BC) of a
node as the fraction of all the shortest paths between every pair of nodes of
the graph passing through the considered node. Let DPG = ($\mathcal{P},E$) be
the graph and $s,t,v\in\mathcal{P}$ three vertexes of DPG, we can denote with
$\sigma(s,t)$ the number of shortest paths between $s$ and $t$ and with
$\sigma(s,t|v)$ the number of shortest paths between $s$ and $t$ passing
through $v$. Then, the BC of the node $v\in\mathcal{P}$ is defined as:

$BC(v)=\sum_{s,t\in\mathcal{P}}\frac{\sigma(s,t|v)}{\sigma(s,t)}.$

All details and observations about BC can be read in [40]. BC serves as a
relevant metric for gaining a deeper insight into the significance of
decisions within the ensemble model. We can observe that a node with a higher
BC value has a more significant influence on the flow of information within
the graph; nodes with high BC can be considered potential bottleneck nodes
because they play a crucial role in facilitating interactions between
different parts of the DPG. For this reason, we can assert that these nodes
are meaningful to understanding the tree-based ensemble models: in all tree
base learners, the decision contained in the node is essential to classify the
elements of the dataset. We highlight that the significance extends beyond the
characteristic itself; it encompasses the value associated with it.

According to Mones et al. [41], we define the _local reaching centrality_
(LRC) of a node $v$ of the DPG as the proportion of other nodes reachable from
node $v$ via outgoing edges. LRC can be generalised to weighted graphs by
measuring the average weight of a given directed path starting from node $v$
(more details are available on [41]). The LRC serves as a metric for assessing
the importance of DPG’s nodes. It gauges the extent to which decisions
contained in these nodes are employed by diverse tree base learners for
classifying samples in the training set. This, in turn, reflects the
importance of these decisions in the classification of new samples. The LRC
offers a comprehensive perspective on the concept of feature importance (FI)
by extending its definition to encompass the values associated with features
across various decisions. Additionally, the prominence of paths between
highlighted predicates indicates their frequent utilisation, providing
insights into how new samples can be classified with fewer decisions.

####  3.3.3 Community.

While there is no single definition of a community, we can observe structures
similar to communities in the DPG. According to Radicchi et al. [42], we
define a _community_ as a subset of nodes of the DPG characterised by dense
interconnections between its elements and sparse connections with the other
nodes of the DPG that do not belong to the community. Based on the properties
of DPG, we employed _asynchronous label propagation_ algorithm, proposed by
Raghavan et al. [43], to detect communities within the graph. The core concept
of the algorithm involves each graph node determining its community membership
based on the majority of its neighbours. Without delving into details, which
can be appreciated in [43], the algorithm comprises a series of steps: each
node initially possesses a unique label. As these labels diffuse through the
graph, closely connected groups of nodes converge on a common label. These
consensus groups then expand outward until further expansion becomes
impractical. After this label propagation process, nodes sharing the same
labels are identified as belonging to the same community. This process is
iterated until each node in the network aligns its label with the community
that includes the maximum number of its neighbouring nodes. The algorithm is
defined asynchronous, as each node receives updates without waiting for
updates on the remaining nodes. Identifying communities in the DPG provides
insights into the ensemble model: visualising them allows us to discover
groups of nodes that similarly contribute to the classification of samples.

By employing the asynchronous label propagation algorithm, we observe that
each formed community is associated with a class. Within these communities,
the features utilised by the ensemble model to classify samples belonging to
the community’s class are emphasised. Once again, the association between
features and values plays a key role, highlighting the specific decisions made
by the learners. To quote Raghavan et al. [43]:

> Communities in social networks can provide insights about common
> characteristics or beliefs among people that make them different from other
> communities.

Similarly, we observe that communities within the DPG offer a valuable
understanding of the characteristics for samples to be assigned to a
particular community class. This intuition extends to identifying predominant
features and those that play a marginal role in the classification process.
Moreover, it is noteworthy that communities also provide insights into the
entire dataset and the complexity of the problem. A community comprising a
substantial number of nodes, each associated with different predicates often
involving distinct features, indicates that the model makes diverse decisions
to assign samples to the community class. This implies that the model
encounters challenges in classifying samples for this particular class, and
data from different classes are not easily distinguishable within the dataset.

Finally, communities, functioning as sub-graphs, can be used to visualise the
decisions made in the ensemble model, enabling the identification of a
specific class. This replaces the complex illustration of the DPG, especially
when we are focused on visualising a single class and dealing with many tree
base learners. We summarised the utility of discussed properties and metrics
in Table 1.

Table 1: Summary of Constraints, Betweenness Centrality (BC), Local Reaching Centrality (LRC), and Community, featuring provided definitions and their utility in offering insights into tree-based ensemble models. Property |  Definition |  Utility
---|---|---
Constraints |  The intervals of values for each feature obtained from all predicates connected by a path that culminates in a given class. |  Calculate the classification boundary values of each feature associated with each class.
BC |  Quantifies the fraction of all the shortest paths between every pair of nodes of the graph passing through the considered node. |  Identify potential bottleneck nodes that correspond to crucial decisions.
LRC |  Quantifies the proportion of other nodes reachable from the local node through its outgoing edges. |  Assess the importance of nodes similarly to feature importance, but enrich the information by encompassing the values associated with features across all decisions.
Community |  A subset of nodes of the DPG which is characterised by dense interconnections between its elements and sparse connections with the other nodes of the DPG that do not belong to the community. |  Understanding the characteristics of nodes to be assigned to a particular community class, identifying predominant predicates, and those that play a marginal role in the classification process.

##  4 Empirical Results and Discussion

In this section, we demonstrate the effectiveness of DPG to the well-known
Iris dataset [8] and a synthetic multiclass
dataset222https://github.com/sbarbonjr/fhg/tree/main/datasets. Each experiment
in this section was conducted using the RF classifier, with variations limited
to the number of tree base learners. The implementation is available
here333https://github.com/sbarbonjr/fhg. Finally, we discuss potential
enhancements to DPG and explore further development opportunities.

###  4.1 DPG: Iris insights

The first case study concerns the classification of the Iris dataset [8]. The
simplicity, manageability, versatility, and relevance of this dataset make it
an interesting and relevant resource for discussions and demonstrations of
interpretability in ML. The dataset comprises measurements of sepals and
petals for iris flowers encompassing three distinct species with a total of
four features and three classes. The RF was selected as the tree-based
ensemble model due to its well-established reputation and high-performance
capabilities. To conduct the classification, we partitioned the dataset into
training and test sets, following a $80$-$20$% proportion, respectively. A
seed value of $42$ was established for randomness control, and the number of
base tree learners was set to $5$. The RF performances, evaluated on the test
set, are summarised in the confusion matrix in Table 2. The model demonstrates
$100$% accuracy.

Table 2: Confusion matrix depicting the performance evaluation of the RF model with $5$ base tree learners on the test set. | Prediction
---|---
Ground truth | Class 0 | Class 1 | Class 2
Class 0 | 19 | 0 | 0
Class 1 | 0 | 13 | 0
Class 2 | 0 | 0 | 13

After training the model, we applied the algorithm outlined in Section 3.2 to
obtain the DPG, which can be visualised in Figure 1.

Figure 1: DPG of the RF composed of $5$ tree base learners trained on Iris
dataset.

Then, we can analyse the obtained graph using the metrics and algorithms
proposed in Section 3.3, verifying their utility and effectiveness in gaining
insights into the model. It is important to note that the DPG leads to the
calculation of both global metrics, referring to the overall graph, and
metrics at the level of individual nodes.

To illustrate the effectiveness and one of the advantages of employing DPG, we
highlight the constraints for the different classes in the Table 3. The class-
specific constraints delineate the necessary characteristics a sample must
exhibit to be assigned to that particular class by the tree-based ensemble
model. This insight contributes to a better understanding of how the model
utilises features for effective classification.

Table 3: Constraints for each class based on the DPG for an RF model within $5$ tree base learners. Class |  Constraints
---|---
0 |  petal width (cm) $\leq$ 1.65
petal length (cm) $\leq$ 2.50
1 |  5.25 < sepal length (cm) $\leq$ 6.05
0.80 < petal width (cm) $\leq$ 1.75
2.45 < petal length (cm) $\leq$ 5.35
2.75 < sepal width (cm) $\leq$ 2.90
2 |  5.75 < sepal length (cm) $\leq$ 6.05
0.80 < petal width (cm) $\leq$ 1.75
2.45 < petal length (cm) $\leq$ 5.35
2.75 < sepal width (cm) $\leq$ 3.10

The first metric under discussion is the BC of the nodes, as depicted in Table
4, where we identify potential bottleneck nodes. These nodes encapsulate
significant information, particularly representing decisions made by numerous
tree base learners. We quickly discern that the decision associated with petal
length (cm) and the value $4.85$ is pivotal, as it is frequently relied upon
by multiple basic learners and is essential for successful classification.

Table 4: Top eight predicates by evaluating their BC obtained from the DPG based on an RF model consisting of $5$ tree base learners. Predicate | BC
---|---
petal length (cm) > 4.85 | 0.053
petal length (cm) <= 4.85 | 0.036
petal width (cm) > 1.55 | 0.034
sepal length (cm) <= 6.05 | 0.032
petal length (cm) > 4.95 | 0.028
petal length (cm) > 4.65 | 0.022
petal width (cm) <= 1.75 | 0.022
petal width (cm) <= 1.55 | 0.021

Furthermore, the LRC metric provides additional information. Examining Table
5(a), we can emphasise the most crucial predicates influencing the decision-
making process of the tree-based ensemble model. This includes not only
identifying the most frequently used features but also recognising the
associated values that lead to significant and divisive splits in the dataset
across various basic learners. As observed in Table 5, a comparison between
the LRC of the nodes and the FI, calculated on the same model on which DPG is
based, suggests that the metric may rank the predicates similarly. FI is
calculated using the _Mean Decrease Impurity_ (MDI) algorithm introduced by
Scornet [44]. This comparison also provides additional information about the
values used in the decisions and the frequency of paths extending the concept
of FI.

Table 5: Comparison of the top eight predicates by evaluating their LRC
obtained from the DPG based on an RF model consisting of $5$ tree base
learners (Table 5(a)), alongside the FI of the same model (Table 5(b))
calculated exploiting MDI algorithm.

(a) LRC evaluation Predicate | LRC
---|---
petal width (cm) <= 1.65 | 1.531
petal length (cm) > 2.45 | 0.919
petal width (cm) > 0.80 | 0.874
petal length (cm) > 2.50 | 0.699
petal width (cm) > 1.65 | 0.618
petal length (cm) <= 5.20 | 0.565
petal width (cm) > 1.55 | 0.540
sepal length (cm) > 5.75 | 0.332

(b) FI evaluation Feature | FI
---|---
petal length (cm) | 0.550
petal width (cm) | 0.373
sepal length (cm) | 0.054
sepal width (cm) | 0.023

By employing the global metric community, we identified the presence of three
distinct communities. Table 6 illustrates the association between each
community and a distinct class obtained by applying the asynchronous label
propagation algorithm to the DPG. We can affirm that each node within a
community contains decisions that significantly contribute to the accurate
classification of samples belonging to a specific class. For instance, when
applying the predicates of Community 3 (comprising two features and two
predicates) to the test set and traversing from the root node, it achieved
$100$% accuracy for Class 0, the class delineated in the mentioned community.

Table 6: Communities obtained from the DPG based on an RF model composed of $5$ tree base learners. The table shows the number of predicates belonging to each community, the number of features in the community nodes, and the class involved in each community. Community | # Predicates | # Features | Class
---|---|---|---
Community 1 | 23 | 4 | 1
Community 2 | 18 | 4 | 2
Community 3 | 3 | 2 | 0

Finally, upon comparing the Table 6 and the Figure 2, we can state that the
communities facilitate the comprehension of how the model addresses the
classification problem. Examining the number of decisions and features
utilised in each community reveals that differentiating between Class 1
(Community 1) and Class 2 (Community 2) poses a greater challenge for the
model. This indicates the difficulty in effectively separating samples within
the dataset into their respective classes. This difficulty becomes apparent
when visualising the dataset across the features, as in Figure 2. Conversely,
the community encompassing Class 0 (Community 3) consists of fewer predicates,
signifying that it is more distinguishable from other classes, as confirmed in
the Figure 2.

Figure 2: Two-dimensional depiction of the Iris dataset, employing feature
pairs in each graph for visual representation.

###  4.2 Comparing to the Graph-based Solutions

As outlined in the Section 2, Gossen and Steffen [7], Murtovi et al. [32]
conducted studies on the interpretability of tree-based ensemble models
exploiting graph structures. We compared DPG with their proposed method by
examining their outcomes and potential insights. Using the same tree-based
ensemble model we studied in Section 4.1 as input, we generated the ADD
displayed in Figure 3. The first noticeable distinction from DPG lies in the
ADD structure, as it forms a bipartite graph. We can observe that the ADD is
generated from the trained model, albeit without fully leveraging the training
dataset. Consequently, the evaluation of connections between nodes and the
assessment of the significance of decisions made by different tree base
learners are not fully exploited. This implies that each branch carries equal
weight and impact in the diagram, and a classification error significantly
influences the structure by introducing an incorrect path.

Figure 3: ADD of an RF model with $5$ tree base learners induced for Iris
dataset.

Another crucial difference is that ADD does not provide graph metrics, leaving
the user the interpretation of the diagram and potentially missing out on
relevant information. Moreover, an additional limitation, as indicated in the
studies by [7, 32], involves the challenge that emerges when generating ADDs
and dealing with large ensembles. Visualisation becomes intricate, even with a
modest count of $20$ tree base learners. In contrast, DPG allows the
computation of both global and local metrics, even with a higher number of
tree base learners.

To further examine these aspects, we use two RF models, one with $20$ tree
learners and the other with $100$, to analyse a complex multiclass problem
with a dataset comprising $4$ classes, $1000$ samples, and $16$ features. This
introduces a four-class problem that was randomly generated. The dataset was
created using the make_classification444https://scikit-
learn.org/stable/modules/generated/sklearn.datasets.make_classification.html
function from scikit-learn. The following setup has been maintained for
training both models. We divided the dataset into training and test sets, with
an $80$-$20$% ratio. We fixed a seed value of $42$ for randomness control to
ensure reproducibility. The RF performances, assessed on the test set, are
summarised in the confusion matrices presented in Table 7. The model with
$100$ tree base learners shows better performance in every parameter, reaching
an overall accuracy of $66$%, outperforming the model with $20$ tree base
learners, which barely reaches $58$%.

Table 7: Confusion matrices of the RF models with $20$ tree base learners (RF 20) and with $100$ tree base learners (RF 100) tested on the synthetic dataset. | Prediction (RF 20) | Prediction (RF 100)
---|---|---
Ground truth | Class 0 | Class 1 | Class 2 | Class 3 | Class 0 | Class 1 | Class 2 | Class 3
Class 0 | 38 | 4 | 12 | 6 | 38 | 4 | 14 | 4
Class 1 | 5 | 31 | 3 | 5 | 4 | 32 | 2 | 6
Class 2 | 11 | 2 | 29 | 2 | 5 | 2 | 33 | 4
Class 3 | 10 | 13 | 10 | 19 | 9 | 9 | 5 | 29

We emphasise that even in this context, DPG is a useful tool. Both DPG and ADD
present intricate visualisations with $20$ tree base learners. However, DPG
overcomes this obstacle by providing metrics that can still offer valid
insights into the model. The first insight is displayed in Table 8, where we
provide constraints for the four classes of the dataset. Constraints, even in
this complex scenario, allow the visualisation of intervals where sample
features should be situated for precise classification into their respective
classes.

Table 8: Constraints for each class based on the DPG for an RF model within $100$ tree base learners. Class 0 | Class 1 | Class 2 | Class 3
---|---|---|---
$-5.87<\texttt{F1}\leq 5.74$ | $-5.79<\texttt{F1}\leq 5.72$ | $-5.76<\texttt{F1}\leq 5.72$ | $-5.76<\texttt{F1}\leq 5.72$
$-2.64<\texttt{F2}\leq 2.63$ | $-2.61<\texttt{F2}\leq 2.61$ | $-2.61<\texttt{F2}\leq 2.61$ | $-2.61<\texttt{F2}\leq 2.63$
$-5.24<\texttt{F3}\leq 3.75$ | $-5.38<\texttt{F3}\leq 3.75$ | $-5.24<\texttt{F3}\leq 3.75$ | $-5.24<\texttt{F3}\leq 3.75$
$-4.80<\texttt{F4}\leq 4.37$ | $-5.15<\texttt{F4}\leq 4.37$ | $-4.80<\texttt{F4}\leq 4.37$ | $-4.80<\texttt{F4}\leq 4.37$
$-2.61<\texttt{F5}\leq 2.44$ | $-2.61<\texttt{F5}\leq 2.71$ | $-2.61<\texttt{F5}\leq 2.44$ | $-2.61<\texttt{F5}\leq 2.44$
$-2.29<\texttt{F6}\leq 2.58$ | $-2.29<\texttt{F6}\leq 2.58$ | $-2.29<\texttt{F6}\leq 2.58$ | $-2.29<\texttt{F6}\leq 2.58$
$-2.82<\texttt{F7}\leq 2.47$ | $-2.82<\texttt{F7}\leq 2.47$ | $-2.82<\texttt{F7}\leq 2.47$ | $-2.82<\texttt{F7}\leq 2.86$
$-4.62<\texttt{F8}\leq 4.74$ | $-4.62<\texttt{F8}\leq 4.74$ | $-4.62<\texttt{F8}\leq 4.74$ | $-4.62<\texttt{F8}\leq 4.74$
$-2.40<\texttt{F9}\leq 2.59$ | $-2.40<\texttt{F9}\leq 2.59$ | $-2.40<\texttt{F9}\leq 2.71$ | $-2.40<\texttt{F9}\leq 2.59$
$-4.71<\texttt{F10}\leq 4.32$ | $-4.71<\texttt{F10}\leq 4.32$ | $-4.71<\texttt{F10}\leq 5.43$ | $-4.71<\texttt{F10}\leq 4.32$
$-2.87<\texttt{F11}\leq 2.77$ | $-2.87<\texttt{F11}\leq 2.77$ | $-2.87<\texttt{F11}\leq 2.86$ | $-2.87<\texttt{F11}\leq 2.77$
$-2.42<\texttt{F12}\leq 2.37$ | $-2.42<\texttt{F12}\leq 2.37$ | $-2.42<\texttt{F12}\leq 2.37$ | $-2.42<\texttt{F12}\leq 2.37$
$-4.28<\texttt{F13}\leq 5.01$ | $-4.28<\texttt{F13}\leq 5.01$ | $-4.28<\texttt{F13}\leq 5.01$ | $-4.28<\texttt{F13}\leq 5.01$
$-7.31<\texttt{F14}\leq 8.33$ | $-7.31<\texttt{F14}\leq 8.33$ | $-7.31<\texttt{F14}\leq 8.33$ | $-7.31<\texttt{F14}\leq 8.33$
$-4.46<\texttt{F15}\leq 4.19$ | $-4.46<\texttt{F15}\leq 4.19$ | $-4.46<\texttt{F15}\leq 4.19$ | $-4.97<\texttt{F15}\leq 4.5$
$-4.70<\texttt{F16}\leq 4.21$ | $-4.70<\texttt{F16}\leq 4.21$ | $-4.70<\texttt{F16}\leq 4.52$ | $-4.70<\texttt{F16}\leq 4.21$

The BC metric helps identifying potential bottleneck nodes. Upon observing
Table 9(a), we can see that there is not a large difference between the BC
values associated with the predicates. Therefore, we can assume that there are
no bottleneck nodes.

Examining the information provided in Table 9(b), the LRC underscores which
predicates significantly impact the decision-making process of the ensemble
model. The predicates F7 <= 1.62 and F1 <= $3.1$ are identified as
particularly crucial.

Table 9: Top eight predicates by evaluating their BC (Table 9(a)), and top
eight predicates by evaluating their LRC (Table 9(b)), both obtained from the
DPG based on an RF model consisting of $100$ tree base learners.

(a) BC evaluation Predicate | BC
---|---
F15 > 1.17 | 0.018
F15 <= 1.61 | 0.015
F12 > 0.20 | 0.015
F12 > 0.41 | 0.014
F4 <= 0.33 | 0.014
F8 > 0.36 | 0.014
F1 <= -1.10 | 0.013
F11 <= 1.16 | 0.013

(b) LRC evaluation Predicate | LRC
---|---
F7 <= 1.62 | 15.812
F1 <= 3.10 | 14.475
F14 > -1.78 | 13.313
F4 > -2.97 | 13.158
F5 > -1.92 | 13.065
F4 > -1.36 | 12.989
F1 <= 2.49 | 12.986
F13 > 1.98 | 12.920

Another insight can be obtained by employing the global metric community. In
this scenario, we identified the presence of four distinct communities,
displayed in Table 10. We note that each community contains a distinct class.
Furthermore, upon observing the table, we can conclude that each community
exhibits a high number of involved features and predicates, confirming the
complexity of the classification problem.

Table 10: Communities obtained from an RF model composed of $100$ tree base learners. The table shows the number of predicates belonging to each community, the number of features in the community nodes, and the class involved in each community. Community | # Predicates | # Features | Class
---|---|---|---
Community 1 | 7767 | 16 | 2
Community 2 | 2149 | 16 | 0
Community 3 | 2351 | 16 | 3
Community 3 | 2100 | 16 | 1

###  4.3 Potential Improvements

Several avenues await exploration in the future. The primary aim is to reduce
the computational cost of DPG, as many real-world problems involve large
datasets that do not scale well with the current implementation of DPG.
Expanding the application scope of DPG is another key goal, including its
utility in explaining models relevant to regression-type problems. Given DPG’s
applicability to any model and dataset, we aim to introduce new tests and use
cases to delve deeper into the method. This includes proposing applications to
novel datasets and exploring their compatibility with other tree-based
ensemble models. Furthermore, while this paper introduces certain metrics and
algorithms derived from graph theory, the field offers extensive possibilities
for future exploration. In the future, we plan to introduce new tools
associated with DPG to enhance the interpretation of tree-based ensemble
models.

##  5 Conclusion

In this paper, we introduced Decision Predicate Graphs (DPG) as a novel model-
agnostic tool for tree-based ensemble interpretability. DPG is obtained from a
trained model and data, ensuring the maintenance of its performance. The
concept behind DPG is to convert an opaque-box tree-based ensemble model into
an enriched graph. DPG enables qualitative measures and the identification of
its predicates, and facilitates comparisons between features and their
associated values, offering insights into the entire model. In particular, we
introduced Betweenness Centrality, Local Reaching Centrality, Community and
Constraints as useful metrics and properties towards improving and extending
the XAI interpretability approaches. While DPG is still considered an evolving
work, its potential is substantial, given the robust underlying theory and the
versatility of the tool. Furthermore, the effervescent research on graphs,
knowledge graphs, and complex networks might strengthen the possibilities
grounded in DPG. As the next step of our current research, we expect to apply
DPG to provide local interpretability and also contribute to improving the
interpretation of regression tasks.

## References

  * [1] Arman Malekloo, Ekin Ozer, Mohammad AlHamaydeh, and Mark Girolami.  Machine learning and structural health monitoring overview with emerging technology and high-dimensional data source highlights.  21(4):1906–1955.  ISSN 1475-9217.  doi: 10.1177/14759217211036880.  Publisher: SAGE Publications.
  * [2] Ibomoiye Domor Mienye and Yanxia Sun.  A survey of ensemble learning: Concepts, algorithms, applications, and prospects.  10:99129–99149.  ISSN 2169-3536.  doi: 10.1109/ACCESS.2022.3207287.  Conference Name: IEEE Access.
  * [3] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  Additive models, trees, and related methods.  In Trevor Hastie, Robert Tibshirani, and Jerome Friedman, editors, _The Elements of Statistical Learning: Data Mining, Inference, and Prediction_ , Springer Series in Statistics, pages 295–336. Springer.
  * Chimatapu et al. [2018] Ravikiran Chimatapu, Hani Hagras, Andrew Starkey, and Gilbert Owusu.  Explainable ai and fuzzy logic systems.  In _Theory and Practice of Natural Computing: 7th International Conference, TPNC 2018, Dublin, Ireland, December 12–14, 2018, Proceedings 7_ , pages 3–20. Springer, 2018.
  * [5] Tin Kam Ho.  Random decision forests.  In _Proceedings of 3rd International Conference on Document Analysis and Recognition_ , volume 1, pages 278–282 vol.1.  doi: 10.1109/ICDAR.1995.598994.
  * [6] Leo Breiman.  Random forests.  45(1):5–32.  ISSN 1573-0565.  doi: 10.1023/A:1010933404324.
  * [7] Frederik Gossen and Bernhard Steffen.  Algebraic aggregation of random forests: towards explainability and rapid evaluation.  25(3):267–285.  ISSN 1433-2787.  doi: 10.1007/s10009-021-00635-x.
  * Fisher [1936] Ronald A Fisher.  The use of multiple measurements in taxonomic problems.  _Annals of eugenics_ , 7(2):179–188, 1936.
  * Guidotti et al. [2018] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi.  A survey of methods for explaining black box models.  _ACM Comput. Surv._ , 51(5), aug 2018.  ISSN 0360-0300.  doi: 10.1145/3236009.
  * [10] Ambreen Hanif, Xuyun Zhang, and Steven Wood.  A survey on explainable artificial intelligence techniques and challenges.  In _2021 IEEE 25th International Enterprise Distributed Object Computing Workshop (EDOCW)_ , pages 81–89.  doi: 10.1109/EDOCW52865.2021.00036.  ISSN: 2325-6605.
  * [11] Amina Adadi and Mohammed Berrada.  Peeking inside the black-box: A survey on explainable artificial intelligence (XAI).  6:52138–52160.  ISSN 2169-3536.  doi: 10.1109/ACCESS.2018.2870052.  Conference Name: IEEE Access.
  * [12] Rudresh Dwivedi, Devam Dave, Het Naik, Smiti Singhal, Rana Omer, Pankesh Patel, Bin Qian, Zhenyu Wen, Tejal Shah, Graham Morgan, and Rajiv Ranjan.  Explainable AI (XAI): Core ideas, techniques, and solutions.  55(9):194:1–194:33.  ISSN 0360-0300.  doi: 10.1145/3561048.
  * [13] Scott M. Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, pages 4768–4777. Curran Associates Inc.  ISBN 978-1-5108-6096-4.
  * Ribeiro et al. [a] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  "why should i trust you?": Explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, pages 1135–1144. Association for Computing Machinery, a.  ISBN 978-1-4503-4232-2.  doi: 10.1145/2939672.2939778.
  * [15] Jerome H. Friedman.  Greedy function approximation: A gradient boosting machine.  29(5):1189–1232.  ISSN 0090-5364.  URL https://www.jstor.org/stable/2699986.  Publisher: Institute of Mathematical Statistics.
  * Ribeiro et al. [b] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Anchors: High-precision model-agnostic explanations.  32(1), b.  ISSN 2374-3468.  doi: 10.1609/aaai.v32i1.11491.  Number: 1.
  * [17] H. Chipman, Edward George, and Robert McCulloch.  Making sense of a forest of trees.  29\.
  * [18] Maissae Haddouchi and Abdelaziz Berrado.  A survey of methods and tools used for interpreting random forest.  In _2019 1st International Conference on Smart Systems and Data Science (ICSSD)_ , pages 1–6.  doi: 10.1109/ICSSD47982.2019.9002770.
  * [19] Massimo Aria, Corrado Cuccurullo, and Agostino Gnasso.  A comparison among interpretative proposals for random forests.  6:100094.  ISSN 2666-8270.  doi: 10.1016/j.mlwa.2021.100094.
  * [20] Morteza Mashayekhi and Robin Gras.  Rule extraction from random forest: the RF+HC methods.  In Denilson Barbosa and Evangelos Milios, editors, _Advances in Artificial Intelligence_ , Lecture Notes in Computer Science, pages 223–237. Springer International Publishing.  ISBN 978-3-319-18356-5.  doi: 10.1007/978-3-319-18356-5_20.
  * [21] Satoshi Hara and Kohei Hayashi.  Making tree ensembles interpretable: A bayesian model selection approach.  In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , pages 77–85. PMLR.  ISSN: 2640-3498.
  * [22] Xun Zhao, Yanhong Wu, Dik Lun Lee, and Weiwei Cui.  iForest: Interpreting random forests via visual analytics.  25(1):407–416.  ISSN 1941-0506.  doi: 10.1109/TVCG.2018.2864475.  Conference Name: IEEE Transactions on Visualization and Computer Graphics.
  * [23] Julian Hatwell, Mohamed Medhat Gaber, and R. Muhammad Atif Azad.  CHIRPS: Explaining random forest classification.  53(8):5747–5788.  ISSN 1573-7462.  doi: 10.1007/s10462-020-09833-6.
  * [24] Mário Popolin Neto and Fernando V. Paulovich.  Explainable matrix - visualization for global and local interpretability of random forest classification ensembles.  27(2):1427–1437.  ISSN 1077-2626.  doi: 10.1109/TVCG.2020.3030354.  Publisher: IEEE Computer Society.
  * [25] Klest Dedja, Felipe Kenji Nakano, Konstantinos Pliakos, and Celine Vens.  BELLATREX: Building explanations through a LocaLly AccuraTe rule EXtractor.  11:41348 – 41367.  ISSN 2169-3536.  doi: 10.1109/ACCESS.2023.3268866.
  * Van Assche and Blockeel [2007] Anneleen Van Assche and Hendrik Blockeel.  Seeing the forest through the trees: Learning a comprehensible model from an ensemble.  In _Machine Learning: ECML 2007: 18th European Conference on Machine Learning, Warsaw, Poland, September 17-21, 2007. Proceedings 18_ , pages 418–429. Springer, 2007.
  * Zhou and Hooker [2016] Yichen Zhou and Giles Hooker.  Interpreting models via single tree approximation, 2016.
  * [28] Houtao Deng.  Interpreting tree ensembles with inTrees.  7(4):277–287.  ISSN 2364-4168.  doi: 10.1007/s41060-018-0144-8.
  * [29] Bogdan Gulowaty and Michał Woźniak.  Extracting interpretable decision tree ensemble from random forest.  In _2021 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8.  doi: 10.1109/IJCNN52387.2021.9533601.  ISSN: 2161-4407.
  * [30] Hiroki Nakahara, Akira Jinguji, Simpei Sato, and Tsutomu Sasao.  A random forest using a multi-valued decision diagram on an FPGA.  In _2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL)_ , pages 266–271.  doi: 10.1109/ISMVL.2017.40.  ISSN: 2378-2226.
  * [31] Olavo A. B. Silva, Alysson K. C. Silva, Ícaro G. S. Moreira, José A. M. Nacif, and Ricardo S. Ferreira.  RDSF: Everything at same place all at once - a random decision single forest.  In _Anais do Simpósio Brasileiro de Engenharia de Sistemas Computacionais (SBESC)_ , pages 31–36. SBC.  ISSN: 2237-5430.
  * [32] Alnis Murtovi, Alexander Bainczyk, Gerrit Nolte, Maximilian Schlüter, and Bernhard Steffen.  Forest GUMP: a tool for verification and explanation.  25(3):287–299.  ISSN 1433-2787.  doi: 10.1007/s10009-023-00702-5.
  * Oliver [1993] Jonathan J. Oliver.  Decision graphs - an extension of decision trees.  1993\.
  * [34] Dmitry Ignatov and Andrey Ignatov.  Decision stream: Cultivating deep decision trees.  In _2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI)_ , pages 905–912.  doi: 10.1109/ICTAI.2017.00140.  ISSN: 2375-0197.
  * [35] Scott Needham and David L. Dowe.  Message length as an effective ockham’s razor in decision tree induction.  In _International Workshop on Artificial Intelligence and Statistics_ , pages 216–223. PMLR.  ISSN: 2640-3498.
  * [36] Peter J. Tan and David L. Dowe.  MML inference of decision graphs with multi-way joins and dynamic attributes.  In Tamás (Tom) Domonkos Gedeon and Lance Chun Che Fung, editors, _AI 2003: Advances in Artificial Intelligence_ , Lecture Notes in Computer Science, pages 269–281. Springer.  ISBN 978-3-540-24581-0.  doi: 10.1007/978-3-540-24581-0_23.
  * [37] Alexandre M. Florio, Pedro Martins, Maximilian Schiffer, Thiago Serra, and Thibaut Vidal.  Optimal decision diagrams for classification.  37(6):7577–7585.  ISSN 2374-3468.  doi: 10.1609/aaai.v37i6.25920.  Number: 6.
  * [38] Bingzhao Zhu and Mahsa Shoaran.  Tree in tree: from decision trees to decision graphs.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 13707–13718. Curran Associates, Inc.
  * [39] Christopher Stewart Wallace.  _Statistical and Inductive Inference by Minimum Message Length_.  Information Science and Statistics. Springer-Verlag.  ISBN 978-0-387-23795-4.  doi: 10.1007/0-387-27656-4.
  * [40] Ulrik Brandes.  On variants of shortest-path betweenness centrality and their generic computation.  30(2):136–145.  ISSN 0378-8733.  doi: 10.1016/j.socnet.2007.11.001.
  * [41] Enys Mones, Lilla Vicsek, and Tamás Vicsek.  Hierarchy measure for complex networks.  7(3):e33799.  ISSN 1932-6203.  doi: 10.1371/journal.pone.0033799.  Publisher: Public Library of Science.
  * [42] Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi.  Defining and identifying communities in networks.  101(9):2658–2663.  doi: 10.1073/pnas.0400054101.  Publisher: Proceedings of the National Academy of Sciences.
  * [43] Usha Nandini Raghavan, Réka Albert, and Soundar Kumara.  Near linear time algorithm to detect community structures in large-scale networks.  76(3):036106.  doi: 10.1103/PhysRevE.76.036106.  Publisher: American Physical Society.
  * [44] Erwan Scornet.  Trees, forests, and impurity-based variable importance.