Pith. sign in

REVIEW 4 major objections 6 minor 35 references

GS-BART: Bayesian Additive Regression Trees with Graph-split Decision Rules

T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Pith's one-line read GS-BART replaces axis-parallel tree cuts with graph-split rules that respect feature topology, improving prediction for spatial and network data.

desk verdict Two internal inconsistencies in the MCMC description (Eq. 7 missing a term; Alg. 2 missing the IIT correction) keep me from trusting the numbers, but the graph-split BART idea is a real, referee-worthy extension. read the letter →

arxiv 2509.07166 v1 pith:MI4CQSRW submitted 2025-09-08 stat.ME

classification stat.ME MSC 62G0862F1562H30
keywords Bayesianadditiveregressiontreesgraph-splitdecisionrulesarborescenceinformedMCMCspatialnetworkspanningnonparametric
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces GS-BART, a Bayesian additive regression tree method whose decision rules split feature graphs instead of cutting one feature at a time. It claims that encoding feature information into candidate directed rooted trees, called arborescences, lets the model form contiguous, topology-respecting partitions that axis-parallel BART cannot express. The authors further claim that a rejection-free informed MCMC sampler, built on recursive gradient message passing and a quadratic likelihood approximation, makes this practical for normal, count, and classification responses. In their experiments, the method substantially reduces out-of-sample prediction error on spatial data, for example a U-shape MSPE of 0.82 versus 3.51 for BART, while staying competitive on unstructured-feature benchmarks.

What carries the argument

The central object is the decision arborescence: a directed rooted tree whose vertices are bins of samples and whose edges encode feature similarity, with the key property that removing one edge yields a valid bipartition that is itself an arborescence. Recursive edge cuts on these arborescences produce the decision tree. The computational engine is a bottom-up recursive message-passing scheme that accumulates leaf-level gradient statistics J and H at each vertex, so the marginal likelihood ratio for every possible valid split can be computed in one pass over each candidate arborescence, in parallel across the candidate graph set. This feeds an informed importance tempering sampler that reweights all neighboring trees by posterior-informed proposal weights and corrects for the likelihood approximation by importance weighting.

What would settle it

Run GS-BART on the U-shape example but supply a deliberately mis-specified graph that connects the two arms of the U-shape across the hole, bypassing the true boundary. If prediction error does not revert to or exceed that of axis-parallel BART, then the topology-respecting advantage is not actually driven by graph fidelity; if it does degrade, the assumption that the graph must encode the true geometry is confirmed.

Watch

Extended reading notes

Core claim

The paper claims that Bayesian additive regression trees can be built on graph-split decision rules rather than axis-parallel cuts, with each weak learner drawing splits by removing edges from candidate arborescences that encode feature structure. Splitting an edge of an arborescence bipartitions the vertex set into two connected components, so spatial or network data are partitioned into contiguous, flexibly shaped regions that respect domain geometry. Standard BART becomes a special case when numerical features are encoded as chain graphs, since an edge cut in a chain is equivalent to a threshold split. The paper also claims that an informed importance tempering sampler, whose proposal weights are computed by a parallel bottom-up message-passing algorithm over arborescences, mixes substantially faster than the standard BART split-merge sampler and extends to non-Gaussian responses through a second-order likelihood approximation. The numerical evidence includes U-shape MSPE of 0.82 versus 3.51 for BART and better or comparable accuracy on network classification.

Load-bearing premise

The claimed gains depend on the user-supplied graphs actually matching the true dependence structure, and the paper states that the manifold or graph relations are currently assumed predefined rather than learned from data.

Editorial extensions

If this is right

  • Spatial regression with irregular boundaries, holes, or sharp discontinuities can be handled by additive trees without the axis-parallel artifacts that appear in standard BART predictions.
  • Because chain-graph encoding reproduces ordinary BART, GS-BART can serve as a drop-in extension that reduces to standard behavior when features are unstructured.
  • The informed sampler removes the need for closed-form marginal likelihoods in non-Gaussian responses, so count and multinomial regression share the same fast mixing machinery as normal regression.
  • Across weak learners, the randomness in the arborescences and Voronoi tessellations enriches the space of possible partitions, and performance stays stable once the number of trees, arborescences, and vertices is sufficiently large.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: if the gains persist when graphs are estimated from covariates rather than supplied, the method would apply to high-dimensional settings where the true manifold or network is unknown, a direction the authors explicitly leave open.
  • Beyond the paper: the graph-split mechanism should transfer to any discrete structure admitting a tree representation, such as hierarchical taxonomies, knowledge graphs, or structured categorical predictors, not only spatial and network data.
  • Beyond the paper: the quadratic-approximation importance correction suggests the informed sampler could be ported to other twice-differentiable likelihoods, but that extension is not tested in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes GS-BART, a Bayesian additive regression tree model in which each split of a decision tree is a bipartition of a user-supplied directed rooted tree (arborescence) that encodes feature structure. Candidate graphs include chains for numerical covariates, random spanning trees of network adjacency graphs, and arborescences built from Voronoi tessellations of spatial domains. The authors introduce an informed MCMC sampler (IIT) that uses a quadratic approximation of the log-likelihood to compute marginal likelihood ratios for all possible split and merge moves, with a recursive message-passing algorithm over arborescences, and they claim that an importance correction makes the sampler target the exact posterior. The method is evaluated on simulated and real spatial, network, count, and classification data against XGBoost, BART, XBART, Gaussian-process, and random-forest baselines.

Significance. If the sampler is implemented in the way the theory intends, GS-BART would be a valuable contribution: graph-respecting partitions are natural for spatial and network data, the recursive computation plausibly reduces the cost of evaluating all candidate splits to O(|V|) per proposal, and the framework unifies standard BART through chain graphs. The paper also reports extensive experiments with sensitivity analyses, uncertainty quantification, and real-data demonstrations, and it is transparent about the user-supplied graph limitation in Section 6. However, the numerical evidence is currently not verifiable: no code is provided, and the pseudocode is inconsistent with the importance-correction theory in two load-bearing places. As written, Algorithm 2 targets the tilted distribution p tilde proportional to p Z rather than the exact posterior p, and Equation (7) defines a J statistic different from the one in Lemma 1. The empirical claims, such as the U-shape MSPE of 0.82 versus 3.51 for BART, are suggestive but cannot be confirmed from the manuscript alone.

major comments (4)
  1. [§4.3, Algorithm 2] The text and pseudocode disagree on the importance correction. Section 4.3 states that the chain P with transition η/Z is reversible with respect to p̃ ∝ p Z and that 'we correct for the bias by importance sampling... this procedure is summarized in Alg. 2', and Supplement S1.1 derives the importance weight w = p/(p̂ Z). Algorithm 2, however, simply iterates K informed proposals, sets T_t to the final proposed tree, and draws M_t from the approximate conditional posterior in Equation (5), with no computation of Z(T_t) as a weight and no weighted resampling or weighted averaging. If the implementation matches the pseudocode, the sampled trees come from p̃, which upweights trees with large normalizing constants Z, and the resulting posterior of tree size, leaf depth, predictive intervals, and variable importance would be biased. The authors must state explicitly whether the implementation includes the 1/Z reweighting and must make Algorithm 2 consistent with the derivation in Supplement S1.1.
  2. [§4.4, Eq. (7)] The definition J_k(v) = Σ_{i∈v∩ξ_k∩[ntrain]} ( ˙Lσ(φ̂_i) − L̈σ(φ̂_i) ) omits the factor φ̂_{t,i} in the second term. Lemma 1 defines J(ξ_k) = Σ_{i∈ξ_k∩[ntrain]} ( ˙Lσ(φ̂_i) − φ̂_{t,i} L̈σ(φ̂_i) ), and the derivation in Supplement S1.3 uses this φ̂_{t,i} term. Because Equation (7) is the input to the recursive split-likelihood computations used for all informed proposals in Section 4.4 and Supplementary Algorithm S3, implementing Equation (7) as written evaluates a different objective and mis-specifies every split likelihood ratio for non-Gaussian models. If this is a typographical omission, it must be corrected; otherwise the recursive algorithm is not computing the marginal likelihood ratios derived in Lemma 1.
  3. [Section 5, Tables 1 and 2] The central empirical claim, for example the U-shape MSPE of 0.82 for GS-BART versus 3.51 for BART in Table 1, cannot be independently verified because no code is released and the pseudocode has the two inconsistencies described above. Since the numerical experiments are the main evidence for the claimed 'superior performance,' the paper should release a reference implementation, or at minimum a precise specification of every step including how the importance weights from S1.1 are computed and how the K IIT samples are aggregated, so that readers can confirm that the reported numbers come from the algorithm as described.
  4. [Section 6, Conclusion] The authors acknowledge that 'the manifold structure or graph relations among data are predefined' in Section 6. This is a substantive limitation of the method's scope: if the candidate arborescences encode an incorrect graph, the graph-split rules will faithfully propagate that misspecification. The paper should state this caveat more prominently in the abstract or introduction and should temper the general claim that GS-BART is superior for spatial and network data, since all experiments use hand-constructed graphs that are favorable to the method.
minor comments (6)
  1. [Section 5, Experiment settings] The sentence 'GS-BART and XBART are run for 215 iterations with a 15-iteration burn-in' appears to be missing a superscript and should read 2^15 iterations; please clarify the exponent throughout.
  2. [Table 2 vs. text] Table 2 reports the King County House sample size as n=20419, while the text and Supplement S3 report n=20149; please reconcile this inconsistency.
  3. [Section 5 and Table S3] The reported numbers of features are inconsistent across the main text and the supplement: US Cancer is given as p=27 in the text but p=29 in Supplement S3, Air Pollution and Flood are p=27 in the text but p=29 in Supplement S3, and US Election is p=55 in the text but Table S3 lists 53 unstructured arborescences. These counts should be unified.
  4. [Section 5, NYC Education] The main text reports NYC Education as n=1690, p=5, while Supplement S3 describes p=6 features and Table S3 lists 7 unstructured arborescences; please reconcile the feature count.
  5. [Section 4.2, notation] The same symbol L_σ appears to be used for both the likelihood and the log-likelihood in the sentences defining L_σ and L_σ; please use distinct notation, such as ℓ_σ for the log-likelihood, to avoid confusion in the Taylor expansion statements.
  6. [Figure 3(B)] The caption of Figure 3(B) says 'posterior predictive standard deviation surface plots of GS-BART, BART and XBART', but the panel labels in the figure show LGP and RFGLS while the text also discusses XBART; please align the caption with the displayed panels or describe the XBART results in a separate figure.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: GS-BART's derivation is self-contained; self-citations are minor and non-load-bearing; the Eq. (7)/Alg. 2 inconsistencies are correctness risks, not circular steps.

full rationale

GS-BART's claimed derivation chain is not circular. The graph-split formulation is defined from user-supplied feature graphs and a tree prior, while the response model (2) and the posterior are independent of the test outcomes used in prediction comparisons. The quadratic log-likelihood approximation in Lemma 1 is used only to build informed proposals, and Supplementary S1.1 supplies an importance weight w(T_t,M_t)=p/(p-hat Z) designed to target the exact posterior, so posterior inference does not reduce to the approximation. The self-citations (Zhou and Smith 2022 for IIT; Luo et al. 2021 for the spanning-tree bipartition property) are methodological or mathematical results whose stated assumptions do not include GS-BART's predictive claim; S1.1 also re-derives the detailed balance condition, so sampler validity is not imported solely by citation. Numerical comparisons are out-of-sample against external baselines such as BART, XGBoost, and Gaussian-process methods, with standard errors reported, and no test labels enter training. The main issues are internal consistency and verifiability rather than circularity: Eq. (7) drops the phi-hat_{t,i} factor that appears in Lemma 1's J(xi_k), and Algorithm 2 omits the importance reweighting that Section 4.3 and S1.1 require. These are correctness risks if the implementation follows the pseudocode, but they are not instances of a result reducing to its inputs. Section 6's admission that manifold or graph relations are assumed predefined is a scope limitation, not a circular step. The score of 2 reflects only minor, non-load-bearing self-citations; the central derivation remains self-contained.

Assumptions & free parameters 7 free parameters · 4 assumptions · 0 invented entities

The central method introduces no new physical or mathematical entities; candidate graphs are constructed from observed features. Free parameters are the standard BART hyperparameters and GS-BART-specific tuning constants, all chosen by hand or via empirical-Bayes rules from training data.

free parameters (7)
  • Tree prior alpha = 0.95
    Default split probability parameter recommended in Section 3.1; chosen by hand, not fitted to data.
  • Tree prior beta = 2
    Default depth penalty parameter recommended in Section 3.1; chosen by hand.
  • Number of weak learners T = 50
    Set to 50 in most experiments; sensitivity analysis in Section S4.2 shows robust performance for T >= 25.
  • Arborescences per structured feature M = 5
    Default number of random arborescences per graph; sensitivity analysis in Section S4.2 shows gains up to M=5 with diminishing returns after.
  • Vertices per arborescence |V| = 100
    Default bin count; Section S4.2 shows accuracy improves up to |V|=100 and then plateaus.
  • Inverse-Gamma prior scale b for sigma_mu^2 = var(y)/T
    Data-driven choice recommended in Section 3.1; depends on training response variance.
  • Residual variance prior parameter lambda = Chosen so P(sigma < sigma_hat) = 0.9
    Standard BART empirical-Bayes setting for normal responses, described in Section S2.
assumptions (4)
  • domain assumption The response log-likelihood is twice differentiable with respect to the latent additively structured mean.
    Invoked in Section 4.1 to justify the quadratic Taylor approximation; satisfied by normal, Poisson, and multinomial models.
  • domain assumption The manifold structure or graph relations among data are predefined by the user.
    State explicitly in Section 6 as a current limitation; if the graph is misspecified, the split rules encode that misspecification.
  • domain assumption A small number of random spanning trees of the neighborhood graph sufficiently covers useful bipartitions of the data.
    Section 3.2 Example 2 relies on Luo et al. (2021) for the bipartition-covering property of spanning trees, but the sufficiency of M=5 random arborescences is empirical, not guaranteed.
  • standard math The informed importance tempering (IIT) framework of Zhou and Smith (2022) provides a valid rejection-free sampler when combined with exact importance weights.
    The detailed balance and reweighting argument in Section S1.1 is standard and derived from the cited framework.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GS-BART: Bayesian Additive Regression Trees with Graph-split Decision Rules." pith.science (2026). https://pith.science/paper/MI4CQSRW

@misc{pith2026250907166,
  author       = {Pith},
  title        = {Pith review of: GS-BART: Bayesian Additive Regression Trees with Graph-split Decision Rules},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MI4CQSRW}},
  note         = {Machine review of arXiv:2509.07166}
}
read the original abstract

Ensemble decision tree methods such as XGBoost, Random Forest, and Bayesian Additive Regression Trees (BART) have gained enormous popularity in data science for their superior performance in machine learning regression and classification tasks. In this paper, we introduce a new Bayesian graph-split additive decision tree method, GS-BART, designed to enhance the performance of axis-parallel split-based BART for dependent data with graph structures. The proposed approach encodes input feature information into candidate graph sets and employs a flexible split rule that respects the graph topology when constructing decision trees. We consider a generalized nonparametric regression model using GS-BART and design a scalable informed MCMC algorithm to sample the decision trees of GS-BART. The algorithm leverages a gradient-based recursive algorithm on root directed spanning trees or chains. The superior performance of the method over conventional ensemble tree models and Gaussian process regression models is illustrated in various regression and classification tasks for spatial and network data analysis.

Figures

Figures reproduced from arXiv: 2509.07166 by the authors.

Figure 1
Figure 1. (A): A graph split decision tree with two internal nodes and three leaf nodes; (B): The →→ [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. (A): An example of the ordered directed edges. Different color denotes different types [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. (A) True and predictive spatial surface plots of [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The partial dependence plots showing spatial effects on log house sales price for GS [PITH_FULL_IMAGE:figures/full_fig_p032_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 32 canonical work pages

  1. [1]

    Anderson, S. C. and Ward, E. J. (2019). Black swans in space: modeling spatiotemporal processes with extremes. Ecology , 100(1):e02403

  2. [2]

    Anselin, L., Syabri, I., and Kho, Y. (2009). GeoDa : an introduction to spatial data analysis. In Handbook of applied spatial analysis: Software tools, methods and applications , pages 73--89. Springer

  3. [3]

    Arvanitidis, G., Hauberg, S., Hennig, P., and Schober, M. (2019). Fast and robust shortest paths on manifolds learned from data. In The 22nd International Conference on Artificial Intelligence and Statistics , pages 1506--1515. PMLR

  4. [4]

    and Fryzlewicz, P

    Blaser, R. and Fryzlewicz, P. (2016). Random rotation ensembles. The Journal of Machine Learning Research , 17(1):126--151

  5. [5]

    A., George, E

    Chipman, H. A., George, E. I., and McCulloch, R. E. (2010). BART : B ayesian additive regression trees. The Annals of Applied Statistics , 4(1):266--298

  6. [6]

    Clauset, A., Newman, M. E. J., and Moore, C. (2004). Finding community structure in very large networks. Phys. Rev. E , 70:066111

  7. [7]

    K., Heaton, M

    Dahl, B. K., Heaton, M. J., Warr, R. L., Fisher, J. D., and Schultz, G. G. (2024). Modeling crash risk on roadway networks using B ayesian regression trees. Technometrics , pages 1--13

  8. [8]

    Deshpande, S. K. (2024). flexbart: Flexible B ayesian regression trees with categorical predictors. Journal of Computational and Graphical Statistics , pages 1--10

Show all 35 references
  1. [9]

    Friedman, J. H. (1991). Multivariate adaptive regression splines. The annals of statistics , 19(1):1--67

  2. [10]

    S., Carreira-Perpi \ n \'a n, M

    Hada, S. S., Carreira-Perpi \ n \'a n, M. \'A ., and Zharmagambetov, A. (2023). Sparse oblique decision trees: A tool to understand and manipulate neural net features. Data Mining and Knowledge Discovery , pages 1--40

  3. [11]

    and Hahn, P

    He, J. and Hahn, P. R. (2023). Stochastic tree ensembles for regularized nonlinear regression. Journal of the American Statistical Association , 118(541):551--570

  4. [12]

    Kelner, J. A. and Madry, A. (2009). Faster generation of random spanning trees. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 13--21. IEEE

  5. [13]

    and Ro c kov \'a , V

    Kim, J. and Ro c kov \'a , V. (2025). On mixing rates for B ayesian CART . Electronic Journal of Statistics , 19(2):3041--3067

  6. [14]

    Li, G., Smith, A., and Zhou, Q. (2023). Importance is important: A guide to informed importance tempering methods. arXiv preprint arXiv:2304.06251

  7. [15]

    Linero, A. R. (2018). B ayesian regression trees for high-dimensional prediction and variable selection. Journal of the American Statistical Association , 113(522):626--636

  8. [16]

    Linero, A. R. (2024). Generalized B ayesian additive regression trees models: Beyond conditional conjugacy. Journal of the American Statistical Association , pages 1--14

  9. [17]

    T., Sang, H., and Mallick, B

    Luo, Z. T., Sang, H., and Mallick, B. (2021). A B ayesian contiguous partitioning method for learning clustered latent variables. Journal of Machine Learning Research , 22(37):1--52

  10. [18]

    T., Sang, H., and Mallick, B

    Luo, Z. T., Sang, H., and Mallick, B. (2022). BAMDT : B ayesian additive semi-multivariate decision trees for nonparametric regression. In International Conference on Machine Learning , pages 14509--14526. PMLR

  11. [19]

    Mohammadi, R., Pratola, M., and Kaptein, M. (2020). Continuous-time birth-death MCMC for B ayesian regression tree models. Journal of Machine Learning Research , 21(201):1--26

  12. [20]

    Murray, J. S. (2021). Log-linear B ayesian additive regression trees for multinomial logistic and count regression models. Journal of the American Statistical Association , 116(534):756--769

  13. [21]

    Y., and Maiti, T

    Nandy, S., Lim, C. Y., and Maiti, T. (2017). Additive model building for spatial regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 79(3):779--800

  14. [22]

    Niu, M., Cheung, P., Lin, L., Dai, Z., Lawrence, N., and Dunson, D. (2019). Intrinsic G aussian processes on complex constrained domains. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 81(3):603--627

  15. [23]

    Niu, M., Dai, Z., Cheung, P., and Wang, Y. (2023). Intrinsic G aussian process on unknown manifolds with probabilistic metrics. Journal of Machine Learning Research , 24(104):1--42

  16. [24]

    Pratola, M. T. (2016). Efficient M etropolis- H astings proposal mechanisms for B ayesian regression tree models. Bayesian Analysis , 11(3):885--911

  17. [25]

    and Van der Pas, S

    Ro c kov \'a , V. and Van der Pas, S. (2020). Posterior concentration for B ayesian regression trees and forests. The Annals of Statistics , 48(4):2108--2131

  18. [26]

    S., Duncan, J., and Yu, B

    Ronen, O., Saarinen, T., Tan, Y. S., Duncan, J., and Yu, B. (2022). A mixing time lower bound for a simplified version of BART . arXiv preprint arXiv:2210.09352

  19. [27]

    Saha, A., Basu, S., and Datta, A. (2023). Random forests for spatially dependent data. Journal of the American Statistical Association , 118(541):665--683

  20. [28]

    and Datta, A

    Saha, A. and Datta, A. (2018). BRISC : bootstrap for rapid inference on spatial covariances. Stat , 7(1):e184

  21. [29]

    Stone, A. J. and Gosling, J. P. (2024). AddiVortes :( B ayesian) additive V oronoi tessellations. Journal of Computational and Graphical Statistics , pages 1--13

  22. [30]

    V., Assun c \ a o, R

    Teixeira, L. V., Assun c \ a o, R. M., and Loschi, R. H. (2019). B ayesian space-time partitioning by sampling and pruning spanning trees. Journal of Machine Learning Research , 20:85--1

  23. [31]

    Voronoi, G. (1908). Nouvelles applications des param \`e tres continus \`a la th \'e orie des formes quadratiques. premier m \'e moire. sur quelques propri \'e t \'e s des formes quadratiques positives parfaites. Journal f \"u r die reine und angewandte Mathematik (Crelles Jou...

  24. [32]

    Zanella, G. (2020). Informed proposals for local MCMC in discrete spaces. Journal of the American Statistical Association , 115(530):852--865

  25. [33]

    and Datta, A

    Zhan, W. and Datta, A. (2025). Neural networks for geospatial data. Journal of the American Statistical Association , 120(549):535--547

  26. [34]

    T., and M \"u ller, P

    Zhang, S., Shih, Y.-C. T., and M \"u ller, P. (2007). A spatially-adjusted B ayesian additive regression tree model to merge two datasets. Bayesian Analysis , 2(3):611--634

  27. [35]

    and Smith, A

    Zhou, Q. and Smith, A. (2022). Rapid convergence of informed importance tempering. In International Conference on Artificial Intelligence and Statistics , pages 10939--10965. PMLR

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.