{"id":"8e3738b7-3e12-43b3-80b5-4344987b3cd3","arxiv_id":"2509.07166","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"GS-BART extends BART to use graph-split decision rules on arborescence encodings of features, with an informed MCMC sampler, and shows predictive gains on spatial and network data.","lead":"The paper introduces GS-BART, a version of Bayesian additive regression trees that splits data along the edges of graph structures such as road networks or county adjacency maps instead of only along single coordinate axes. This lets the model respect spatial and network geometry, and the authors report better predictions on several spatial and network datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MCMC sampler description is internally inconsistent: Eq. (7) drops a term and Alg. 2 omits the importance reweighting required by the theory; without code, reported gains are unverifiable.","rationale":"The reader's weakest assumption concerned sensitivity to user-specified graphs. That is a real limitation but is explicitly acknowledged in Section 6 and does not threaten the validity of the reported experiments, where the graphs are correctly constructed from known coordinates and adjacencies. A more fundamental threat is that the computational algorithm, which is the paper's second main contribution, may not be correctly specified. The typo in Eq. (7) and the missing reweighting in Alg. 2 are concrete, checkable inconsistencies. If the implementation follows the paper, the sampler is biased; if it does not, the paper omits essential steps. Either way, the lack of code makes the headline empirical claim unverifiable. This justifies the reader's CONDITIONAL verdict, but for a different reason than the one they emphasized.","tokens_in":34138,"tokens_out":12507,"duration_ms":105778,"concrete_test":"Request the authors' code and re-run the U-shape simulation (n=800, p=5) under three conditions: (A) the algorithm exactly as stated in the paper (Eq. (7) without the ϕ̂ term, Alg. 2 without reweighting); (B) the algorithm with Eq. (7) corrected and with the S1.1 importance reweighting implemented; (C) the algorithm with only one of the two fixes. If condition (A) does not reproduce the reported MSPE of 0.82 (within sampling error), the paper's description does not match its experiments; if (A) does reproduce it, the exact-posterior claim is demonstrably false and results should be reframed as approximate inference.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim rests on the numerical experiments, which in turn depend on the correctness of the proposed IIT sampler. Two internal inconsistencies prevent verification. First, Eq. (7) defines J_k(v) = Σ( ˙Lσ(ϕ̂_i) − ¨Lσ(ϕ̂_i) ), omitting the ϕ̂_{t,i} factor that appears in the definition of J(ξ_k) in Lemma 1 and in the derivation of S1.3. This J statistic is used in Section 4.4 to compute all split likelihood ratios, so if implemented as written the recursive algorithm evaluates a different objective. Second, Section 4.3 and Supplementary S1.1 state that the IIT sampler must correct the bias of the chain P (which targets p̃ ∝ p Z) by importance reweighting with weights proportional to 1/Z(T), yet Algorithm 2 simply proposes and accepts a sequence of trees and returns the final T_t with no weighting or resampling. If the implementation follows the pseudocode, the sampler targets p̃, not the exact posterior p, biasing tree size and leaf depth. The authors do not release code, so readers cannot determine whether the impressive U-shape MSPE (0.82 vs 3.51) is produced by the described algorithm, a corrected version, or an alternative heuristic. This is more load-bearing than the acknowledged graph-misspecification limitation, because it questions the validity of the empirical evidence itself.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":34509,"tokens_out":7476,"duration_ms":64931,"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":[{"comment":"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.","section":"§4.3, Algorithm 2"},{"comment":"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":"§4.4, Eq. (7)"},{"comment":"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":"Section 5, Tables 1 and 2"},{"comment":"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.","section":"Section 6, Conclusion"}],"minor_comments":[{"comment":"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.","section":"Section 5, Experiment settings"},{"comment":"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":"Table 2 vs. text"},{"comment":"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":"Section 5 and Table S3"},{"comment":"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":"Section 5, NYC Education"},{"comment":"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.","section":"Section 4.2, notation"},{"comment":"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.","section":"Figure 3(B)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of the journal, and the core idea is promising. My main concern is that the reported numerical superiority cannot be checked without code and with the current inconsistencies between the theory and the pseudocode. I would encourage the editor to require the authors to correct Equation (7), make Algorithm 2 implement the importance reweighting described in S1.1, and release a reference implementation before the paper is accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read of GS-BART. The core idea is a genuine extension: encode features as candidate arborescences, split by edge cuts, generalize to non-Gaussian responses, and use an informed importance tempering (IIT) sampler with recursive message passing. Standard BART falls out as a chain-graph special case. That's a useful combination, and the experiments are broad—synthetic U-shape/torus/Friedman plus real spatial and network data. The recursive computation of split likelihood ratios is a real engineering contribution.\n\nBut I have two specific concerns, and they are load-bearing. First, Equation (7) defines J_k(v) = Σ( L̇ − L̈) without the φ̂_{t,i} that appears in Lemma 1's J(ξ_k) and throughout the derivation in S1.3. That is not a cosmetic typo: it's the quantity the recursive algorithm computes for every candidate split. If implemented as written, the split ratios are wrong. Second, Section 4.3 and S1.1 say the IIT chain targets p̃ ∝ p·Z and must be corrected by importance weights proportional to 1/Z. Algorithm 2 shows no such correction—it just proposes, accepts, and returns the last tree. If the code follows the pseudocode, the sampler targets p̃, biasing tree depth and leaf size. These two issues mean the reported gains (U-shape MSPE 0.82 vs 3.51) are not verifiable from the paper, and no code is provided. Maybe both are presentation slip-ups, but I can't tell.\n\nLesser issues: the classification gains are modest (e.g., 91.47 vs 91.62 for XGBoost on U-shape), and real-data comparisons in Table 2 lack repeated-run uncertainty. The graph-misspecification limitation is acknowledged in Section 6; I don't hold that against them.\n\nThe mathematical framework is coherent and the prior art is cited properly (Luo et al. 2022, Deshpande 2024). The novelty is incremental but real. I think the central idea probably works, and a corrected version would be a solid paper. In its current form, I would not take the numerical claims at face value. I'd send it to a serious referee—this deserves a revision cycle, not a desk rejection—but the authors need to fix Eq. (7), reconcile Algorithm 2 with the IIT theory, and release code or a detailed correction.","headline":"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.","tokens_in":34989,"tokens_out":3523,"would_cite":false,"duration_ms":30859,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","62F15","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"GS-BART replaces axis-parallel tree cuts with graph-split rules that respect feature topology, improving prediction for spatial and network data.","keywords":["Bayesian additive regression trees","graph-split decision rules","arborescence","informed MCMC","spatial regression","network regression","spanning trees","nonparametric regression"],"falsifier":"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.","tokens_in":33981,"feed_emoji":"🗺️","tokens_out":5361,"duration_ms":47904,"temperature":0.7,"pith_summary":"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.","feed_headline":"Graph-split BART beats axis-parallel BART on spatial data","feed_subtitle":"Topology-aware tree splits cut U-shape prediction error from 3.51 to 0.82 versus BART.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the original BART model, the additive tree structure, and the default tree prior that GS-BART extends.","marker":"Chipman et al. (2010)"},{"why":"Provides the informed importance tempering framework that makes the rejection-free tree sampler valid.","marker":"Zhou and Smith (2022)"},{"why":"Proves that arbitrary graph bipartitions can be induced by removing an edge from some spanning tree, motivating the use of random arborescences as candidate graphs.","marker":"Luo et al. (2021)"},{"why":"Earlier work using random spanning tree cuts for structured categorical predictors; serves as a related method and comparison baseline.","marker":"Deshpande (2024)"},{"why":"Generalized BART for non-Gaussian responses; the comparison baseline for count-data experiments.","marker":"Linero (2024)"},{"why":"Provides XBART, a stochastic-search tree ensemble baseline, and the idea of learning the leaf-scale parameter from data.","marker":"He and Hahn (2023)"},{"why":"Fast approximately uniform random spanning tree generation used to build the candidate graph sets.","marker":"Kelner and Madry (2009)"},{"why":"Defines informed proposal balancing functions, including the square-root function used in the IIT proposal weights.","marker":"Zanella (2020)"},{"why":"AddiVortes, a Voronoi-tessellation additive tree baseline that the paper compares against and extends with graph-based bipartitions.","marker":"Stone and Gosling (2024)"}],"fun_headline_variants":["Topology-aware tree splits beat axis cuts in BART","Graph-split BART cuts U-shape error 4x on spatial data","BART with graph splits: flexible regions, faster mixing","GS-BART: Bayesian trees that respect graph structure"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Topology-aware tree splits beat axis cuts in BART","Graph-split BART cuts U-shape error 4x on spatial data","BART with graph splits: flexible regions, faster mixing","GS-BART: Bayesian trees that respect graph structure"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000162,"raw_usage":{"total_tokens":1222,"prompt_tokens":909,"completion_tokens":313,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":242}},"tokens_in":525,"tokens_out":313,"duration_ms":3308,"temperature":1.0,"reasoning_tokens":242,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:12:22.546145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"and Smith, A","cited_arxiv_id":null,"evidence_quote":"Provides the informed importance tempering framework that makes the rejection-free tree sampler valid."},{"cited_title":"T., Sang, H., and Mallick, B","cited_arxiv_id":null,"evidence_quote":"Proves that arbitrary graph bipartitions can be induced by removing an edge from some spanning tree, motivating the use of random arborescences as candidate graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier work using random spanning tree cuts for structured categorical predictors; serves as a related method and comparison baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Generalized BART for non-Gaussian responses; the comparison baseline for count-data experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Fast approximately uniform random spanning tree generation used to build the candidate graph sets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines informed proposal balancing functions, including the square-root function used in the IIT proposal weights."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"AddiVortes, a Voronoi-tessellation additive tree baseline that the paper compares against and extends with graph-based bipartitions."}],"review_version":2}