Draft:Decision Predicate Graphs

• Comment: This is pitched more as an essay. The lead would only make sense to someone familiar with the subject matter, which is not the point of a lead. It needs to give a common sense explanation to an intelligent reader.
  Also you have not declared the conflict of interest WP:COI ChrysGalley (talk) 10:33, 9 April 2026 (UTC)

---

Decision Predicate Graph (DPG) is a graph-based method in explainable artificial intelligence (XAI) for the global interpretation of tree-based ensemble models, especially classification models such as random forests. It was introduced as a post hoc, model-specific explanation approach designed to represent the decision structure of trained ensembles while preserving relations among features, thresholds, logical operations and predictions. More broadly, graph-based and structural explanation methods form part of a wider effort in XAI to improve the interpretability and evaluation of machine learning systems.

Overview

In the original formulation, a DPG is a directed weighted graph whose nodes correspond to predicates extracted from the internal nodes and leaves of the trees in an ensemble, while its edges encode the frequency with which training samples satisfy consecutive predicates within base learners. The method was proposed for tree-based ensemble classifiers and aimed at providing a global explanation of model behavior rather than only local or instance-level explanations.

This emphasis on global structure places DPG within a broader class of explanation methods concerned with model-level understanding, explanatory scope and structural interpretability.

Method

In the original formulation, DPG construction proceeds by traversing each tree in the ensemble with training samples, recording the predicate paths followed by the samples, and aggregating those paths into a single graph. The resulting graph can then be analyzed to derive summaries of the ensemble’s behavior using graph-based measures.

The original DPG paper described several interpretive components:

• Constraints, intended to summarize class-specific intervals or boundary-like conditions associated with features.
• Betweenness centrality, used to identify bottleneck predicates that lie on many shortest paths in the graph.
• Local reaching centrality, used to estimate the importance of predicates in terms of reachable downstream structure.
• Community detection, used to identify densely connected groups of predicates that may correspond to class-related substructures.

These components reflect broader concerns in XAI regarding explanation quality, structural comprehensibility and the evaluation of global explanations.

Predicates and relation to decision trees

In DPG, a predicate is a logical condition extracted from a split in a decision tree, usually written as a feature, an operator and a value. Examples from the Iris classification problem include conditions such as petal width (cm) ≤ 1.7 and petal length (cm) ≤ 4.85. In the original formulation, predicates are obtained from the internal split nodes of the trees in the ensemble, while class labels at the leaves are also represented in the graph structure.

For example, in an ensemble trained on the Iris data set, a tree may contain the split petal width (cm) ≤ 1.7. In DPG, that split becomes a node in the graph. If, along a decision path, it is followed by another condition such as petal length (cm) ≤ 4.85, the graph may contain a directed edge between these two predicate nodes, weighted by how often training samples satisfy them consecutively across the ensemble.

DPG differs from a decision tree in both purpose and structure. A decision tree is primarily a predictive model: it receives an input instance and traverses a single path from the root to a leaf in order to output a class or value. By contrast, DPG is an explanatory structure built after training, designed to summarize the decision logic of an entire tree ensemble rather than to make predictions directly. This distinction is consistent with common XAI taxonomies separating predictive models from post hoc explanation methods.

Relation to other explainability methods

The original DPG paper positioned the method in relation to graph-based representations of ensembles such as algebraic decision diagrams, and to broader XAI methods including model-agnostic and rule-extraction approaches. More generally, the method can be situated within ongoing efforts in XAI to define, structure and evaluate explanations not only in terms of predictive usefulness, but also in terms of comprehensibility, correctness and explanatory scope.

See also

• Explainable artificial intelligence
• Random forest
• Decision tree
• Graph theory