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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.
- [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.
- [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)
- [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.
- [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.
- [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.
- [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.
- [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.
- [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
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
free parameters (7)
- Tree prior alpha =
0.95
- Tree prior beta =
2
- Number of weak learners T =
50
- Arborescences per structured feature M =
5
- Vertices per arborescence |V| =
100
- Inverse-Gamma prior scale b for sigma_mu^2 =
var(y)/T
- Residual variance prior parameter lambda =
Chosen so P(sigma < sigma_hat) = 0.9
assumptions (4)
- domain assumption The response log-likelihood is twice differentiable with respect to the latent additively structured mean.
- domain assumption The manifold structure or graph relations among data are predefined by the user.
- domain assumption A small number of random spanning trees of the neighborhood graph sufficiently covers useful bipartitions of the data.
- 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.
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
Reference graph
Works this paper leans on
-
[1]
Anderson, S. C. and Ward, E. J. (2019). Black swans in space: modeling spatiotemporal processes with extremes. Ecology , 100(1):e02403
work page 2019
-
[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
work page 2009
-
[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
work page 2019
-
[4]
Blaser, R. and Fryzlewicz, P. (2016). Random rotation ensembles. The Journal of Machine Learning Research , 17(1):126--151
work page 2016
-
[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
2010
-
[6]
Clauset, A., Newman, M. E. J., and Moore, C. (2004). Finding community structure in very large networks. Phys. Rev. E , 70:066111
work page 2004
-
[7]
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
work page 2024
-
[8]
Deshpande, S. K. (2024). flexbart: Flexible B ayesian regression trees with categorical predictors. Journal of Computational and Graphical Statistics , pages 1--10
work page 2024
Show all 35 references
-
[9]
Friedman, J. H. (1991). Multivariate adaptive regression splines. The annals of statistics , 19(1):1--67
1991
-
[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
2023
-
[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
2023
-
[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
2009
-
[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
2025
-
[14]
Li, G., Smith, A., and Zhou, Q. (2023). Importance is important: A guide to informed importance tempering methods. arXiv preprint arXiv:2304.06251
2023 arXiv
-
[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
2018
-
[16]
Linero, A. R. (2024). Generalized B ayesian additive regression trees models: Beyond conditional conjugacy. Journal of the American Statistical Association , pages 1--14
2024
-
[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
2021
-
[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
2022
-
[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
2020
-
[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
2021
-
[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
2017
-
[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
2019
-
[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
2023
-
[24]
Pratola, M. T. (2016). Efficient M etropolis- H astings proposal mechanisms for B ayesian regression tree models. Bayesian Analysis , 11(3):885--911
2016
-
[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
2020
-
[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
2022 arXiv
-
[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
2023
-
[28]
and Datta, A
Saha, A. and Datta, A. (2018). BRISC : bootstrap for rapid inference on spatial covariances. Stat , 7(1):e184
2018
-
[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
2024
-
[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
2019
-
[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...
1908
-
[32]
Zanella, G. (2020). Informed proposals for local MCMC in discrete spaces. Journal of the American Statistical Association , 115(530):852--865
2020
-
[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
2025
-
[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
2007
-
[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
2022
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.